O2 - Ovládač 2

Na diaľkovom ovládači IPTV je možné zadávať aj názvy staníc, resp. ovládať vstavané aplikácie ako z klávesnice. Navrhnite rozloženie písmen na tlačidlách aj pre Japoncov! Japonská abeceda má veľa znakov a je nutné, aby každý znak bolo možné napísať na novom ovládači. Na ovládač sa však nezmestí veľa tlačidiel, a preto je nutné, aby sa niektoré znaky písali viacnásobným stlačením daného tlačidla. Aby bolo ovládanie jednoduché, znaky musia byť zoradené podľa abecedy (a to aj na každom tlačidle). Samozrejme by sme chceli, aby sa často používané znaky písali na čo najmenej stlačení.

Úloha

Ovládač má presne N tlačidiel a abeceda má M znakov. Ďalej vieme, ako často sa ktorý znak používa. Vašou úlohou je rozdeliť znaky na všetky tlačidlá (v abecednom poradí) tak, aby súčet cien všetkých znakov bol čo najmenší.

Cena jedného znaku je daná súčinom: počet stlačení tlačidla (na ktorom sa znak nachádza) potrebný na výpis znaku * výskyt znaku.

Výskyt znaku je číslo od 1 do 9 – čím je vyššie, tým sa znak častejšie vyskytuje.

Vstup

Na prvom riadku vstupu je číslo N – počet tlačidiel a číslo M – počet znakov. Ďalej nasleduje M riadkov. Na i-tom riadku je číslo, ktoré udáva výskyt i-teho znaku.

O1

N = 9
9 ≤ M ≤ 25

O2

1 ≤ N ≤ 40
N ≤ M ≤ 1400

Výstup

Na výstupe má byť práve jedno číslo, ktoré udáva minimálny súčet cien všetkých znakov.

Príklad O1

Vstup:

9 9
1
1
1
1
1
1
1
1
1

Výstup:

9

Príklad O2

Vstup:

2 3
1
1
1

Výstup:

4

Jedno z optimálnych rozdelení znakov na ovládači je:
prvé tlačidlo: prvý znak, druhý znak
druhé tlačidlo: tretí znak

Cena je potom:
1*1 + 2*1 + 1*1 = 4