Yungom
After getting her Ph.D in Cooking with her research paper on "How to Prepare a Pizza", and another Ph.D in Medicine for finding cures for H.I.V and Alzheimers, Dae Jang Guem (Called Yungom in Persian) decided to solve yet another open problem in Information Theory that even Shanon (the father of Information Theory) failed to solve. She is going to construct a language of n words with d given characters c_1, c_2, …, c_d. This language should be prefix free which means that there is no pair of words like (s, t) in which the word s is a prefix of t. Each character c_i has a usage cost of w_i. The cost of a word s with the length l is the sum of the costs of its l characters. For example, if c_1=a; c_2=b; w_1=1 and w_2=10, the cost of word "aba" is 1+10+1=12. Similarly, the cost of a language with n words is equal to the sum of the costs of its n words. For example, the cost of language "ab"; "bbb"; "baaa" is 11+30+13=54.
Like her previous jobs, Yungom is going to do this task perfectly which means that she wants to find the minimum cost, prefix free language with n words.
Input
There are multiple test cases in the input. Each test case starts with a line containing two integers n (1 ≤ n ≤ 200) and d (1 ≤ d ≤ 200). The next line contains nonnegative integers w_1, w_2, …, w_d. The input is terminated by a line containing two zero numbers.
Output
For each test case, you should print the minimum cost of a prefix free language with n words and d characters.