In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].

If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.

Alphabet consists of 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 is the sum of weights of all letters in this word. A language over an alphabet 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 , from this language is not a prefix of . We want to find out what is the minimal possible weight of an -element, prefixless language over an alphabet .

Assume that , the weight of the letter — and the weight of the letter — . Then the weight of the word — . . The weight of the language — . The language is not prefixless, since the word is a prefix of . The lightest tree-element, prefixless language over the alphabet (assuming that weights of the letters are as before) is ; its weight is .

Write a program that:

- reads two integers and the weights of letters of an alphabet from the standard input;
- computes the minimal weight of a prefixless, -element language over the alphabet ;
- writes the result to the standard output.

In the first line of the standard input there are two positive integers and separated by a single space, (, ). These are the number of words in a language and the number of letters in an alphabet respectively. The second line contains positive integers separated by single spaces. Each of them is not greater than . The -th number is the weight of the -th letter.

In the first and only line of the standard output there should be written one integer — the weight of the lightest prefixless -element language over the alphabet .

For the input data:

3 2 2 5

the correct result is:

16

*Task author: Wojciech Rytter.*