LITELANG - The lightest language

Alphabet Ak 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 Ak is the sum of weights of all letters in this word. A language over an alphabet Ak 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 n-element, prefixless language over an alphabet Ak.

Example

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

Task

Write a program that for each test case:

  • reads two integers n, k and the weights of k letters of an alphabet Ak;
  • computes the minimal weight of a prefixless, n-element language over the alphabet Ak;
  • outputs the result.

Input

The number of test cases t is in the first line of input, then t test cases follow separated by an empty line.

In the first line of a test case 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

For each test case you should output one line with the weight of the lightest prefixless n-element language over the alphabet Ak.

Example

Sample input:
1
3 2
2 5

Sample output:
16

Added by:MichaƂ Czuczman
Date:2004-08-10
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:5th Polish Olympiad in Informatics, stage 3 (Wojciech Rytter)

hide comments
2012-08-30 15:06:18 Hector Navarro
Nice problem, I really enjoyed it!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.