题面缺失。原题面如下:

Description

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

Assume that k=2k = 2, the weight of the letter aW(a)=2W(a) = 2 and the weight of the letter bW(b)=5W(b) = 5. Then the weight of the word abW(ab)=2+5=7W(ab) = 2 + 5 = 7. W(aba)=2+5+2=9W(aba) = 2 + 5 + 2 = 9. The weight of the language J={ab,aba,b}J = \{ab, aba, b\}W(J)=21W(J) = 21. The language JJ is not prefixless, since the word ab is a prefix of aba. The lightest tree-element, prefixless language over the alphabet A2 (assuming that weights of the letters are as before) is {b, aa, ab}; its weight is 16.

Write a program that:

reads two integers n, k and the weights of k letters of an alphabet Ak from the standard input; computes the minimal weight of a prefixless, n-element language over the alphabet Ak; writes the result to the standard output. Input In the first line of the standard input there are two positive integers n and k separated by a single space, (2 ≤ n ≤ 10,000, 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 10,000. The i-th number is the weight of the i-th letter.

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

Sample Input 1 3 2 2 5 Sample Output 1 16

0 comments

No comments so far...

Information

ID
2923
Time
1000ms
Memory
256MiB
Difficulty
10
Tags
(None)
# Submissions
4
Accepted
3
Uploaded By