Dany jest alfabet A_k złożony z k 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 A_k nazywamy sumę wag wszystkich jego liter. Językiem nad alfabetem A_k 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 n-elementowego, bezprefiksowego języka nad alfabetem A_k.

Przykład

Załóżmy, że k = 2 , waga litery a — W(a) = 2 oraz waga litery b — W(b) = 5. Wtedy: waga słowa ab — W(ab) = 2 + 5 = 7. W(aba) = 2 + 5 + 2 = 9. Waga języka J = {ab, aba, b} — W(J) = 21. Język J nie jest bezprefiksowy, ponieważ jego słowo ab jest prefiksem słowa aba. Najlżejszym trzyelementowym bezprefiksowym językiem nad alfabetem A₂ , o określonych powyżej wagach liter, jest {b, aa, ab}; jego waga wynosi 16.

Zadanie

Napisz program, który:

• wczytuje z pliku tekstowego NAJ.IN dwie liczby naturalne n oraz k, a następnie wagi wszystkich k liter alfabetu A_k;
• oblicza najmniejszą wagę bezprefiksowego n-elementowego języka nad alfabetem A_k;
• zapisuje wynik w pliku tekstowym NAJ.OUT.

Wejście

W pierwszym wierszu pliku wejściowego NAJ.IN znajdują się dwie dodatnie liczby całkowite n i k oddzielone pojedynczym odstępem (2<=n<=10000, 2<=k<=26). Są to odpowiednio: liczba słów języka i liczba liter alfabetu. Drugi wiersz zawiera k dodatnich liczb całkowitych nie większych niż 10000, oddzielonych pojedynczymi odstępami — i-ta liczba jest wagą i-tej litery.

Wyjście

W pierwszym i jedynym wierszu pliku wyjściowego NAJ.OUT Twój program powinien wypisać jedną liczbę całkowita — wagę najlżejszego, bezprefiksowego, n-elementowego języka nad alfabetem A_k.

Przykład

Dla pliku wejściowego NAJ.IN:

3 2
2 5

16

Twój program powinien szukać pliku NAJ.IN w katalogu bieżącym i tworzyć plik NAJ.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę NAJ.??? gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonalnej powinien być zapisany w pliku NAJ.EXE.