


The lightest language
Alphabet A_{k} consists of k initial letters of English alphabet. A positive integer called a weight is assigned to each letter of the alphabet. A weight of a word built from the letters of the alphabet A_{k} is the sum of weights of all letters in this word. A language over an alphabet A_{k} is any finite set of words built from the letters of this alphabet. A weight of a language is the sum of weights of all its words. We say that the language is prefixless if for each pair of different words w, v from this language w is not a prefix of v. We want to find out what is the minimal possible weight of an nelement, prefixless language over an alphabet A_{k}. ExampleAssume that k = 2 , the weight of the letter a  W(a)=2 and the weight of the letter b  W(b) = 5. The weight of the word ab  W(ab)= 2+5=7. W(aba)=2+5+2=9. The weight of the language J = {ab, aba, b}  W(J) = 21. The language J is not prefixless, since the word ab is a prefix of aba. The lightest treeelement, prefixless language over the alphabet A_{2} (assuming that weights of the letters are as before) is {b, aa, ab}; its weight is 16. TaskWrite a program that:
InputIn the first line of the input file NAJ.IN there are two positive integers n and k separated by a single space, (2<=n<=10000, 2<=k<=26). These are the number of words in a language and the number of letters in an alphabet respectively. The second line contains k positive integers separated by single spaces. Each of them is not greater than 10000. The ith number is the weight of the ith letter. OutputIn the first and only line of the output file NAJ.OUT there should be written one integer  the weight of the lightest prefixless nelement language over the alphabet A_{k}. ExampleFor the input file NAJ.IN: 3 2 2 5the correct result is the output file NAJ.OUT: 16 