## The lightest language

## POI V Stage 3 Problem 4## The lightest language
Alphabet A
We want to find out what is the minimal possible weight of an n-element,
prefixless language over an alphabet A ## Example
Assume 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 tree-element, prefixless language over the alphabet
A ## TaskWrite a program that: - reads two integers n, k and the weights of k letters of
an alphabet
A
_{k}from the text file NAJ.IN; - computes the minimal weight of a prefixless, n-element
language over the alphabet A
_{k}; - writes the result to the text file NAJ.OUT.
## 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 i-th number is the weight of the i-th letter. ## Output
In the first and only line of the output file NAJ.OUT
there should be written one integer - the weight of
the lightest prefixless n-element language over the alphabet
A ## Sample Input3 2 2 5 ## Sample Output16SubmitStatistics |