C2 - Mobil

Navrhnite nový mobil s tlačidlami pre Japoncov! Japonská abeceda má veľa znakov a je nutné, aby každý znak bolo možné napísať na novom mobile. Na mobil 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

Nový mobil má presne N kláves 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 kláves a číslo M – počet znakov. Ďalej nasleduje M riadkov. Na i-tom riadku je číslo, ktoré udáva výskyt i-teho znaku.

C1

N = 9
9 ≤ M ≤ 25

C2

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 C1

Vstup:

9 9
1
1
1
1
1
1
1
1
1

Výstup:

9

Príklad C2

Vstup:

2 3
1
1
1

Výstup:

4

Optimálne rozdelenie znakov na klávesy je:
prvý kláves: prvý znak, druhý znak
druhý kláves: tretí znak

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