Najlżejszy język

Limit pamięci: 32 MB

Dany jest alfabet złożony z początkowych liter alfabetu angielskiego. Każda litera w tym alfabecie ma określoną wagę, która jest dodatnią liczbą całkowitą. Wagą słowa zbudowanego z liter alfabetu nazywamy sumę wag wszystkich jego liter. Językiem nad alfabetem nazywamy dowolny skończony zbiór różnych słów utworzonych z liter tego alfabetu. Wagą języka nazywamy sumę wag wszystkich jego słów.

Mówimy że język jest bezprefiksowy, gdy żadne jego słowo nie jest prefiksem (początkiem) jego innego słowa. Chcemy ustalić, jaka może być najmniejsza waga -elementowego, bezprefiksowego języka nad alfabetem .

Przykład

Załóżmy, że , waga litery — oraz waga litery — . Wtedy: waga słowa — . . Waga języka — . Język nie jest bezprefiksowy, ponieważ jego słowo jest prefiksem słowa . Najlżejszym trzyelementowym bezprefiksowym językiem nad alfabetem , o określonych powyżej wagach liter, jest ; jego waga wynosi .

Zadanie

Napisz program, który:

• wczytuje ze standardowego wejścia dwie liczby naturalne oraz , a następnie wagi wszystkich liter alfabetu ;
• oblicza najmniejszą wagę bezprefiksowego -elementowego języka nad alfabetem ;
• zapisuje wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie dodatnie liczby całkowite i oddzielone pojedynczym odstępem . Są to odpowiednio: liczba słów języka i liczba liter alfabetu. Drugi wiersz zawiera dodatnich liczb całkowitych nie większych niż , oddzielonych pojedynczymi odstępami — -ta liczba jest wagą -tej litery.

Wyjście

W pierwszym i jedynym wierszu standardowego wyjścia Twój program powinien wypisać jedną liczbę całkowitą — wagę najlżejszego, bezprefiksowego, -elementowego języka nad alfabetem .

Przykład

Dla danych wejściowych:

3 2
2 5

poprawną odpowiedzią jest:

16

Autor zadania: Wojciech Rytter.