HPREFIX - 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 Alzheimer's, 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 c1, c2, ... cd. 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 ci has a usage cost of wi. The cost of a word s with the length l is the sum of the costs of its l characters. For example, if c1=a; c2=b; w1=1 and w2=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 w1,w2, ... wd. 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.

Sample
Input
3 4
1 10 100 1000
0 0

Output
23


Added by:DVH
Date:2013-11-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ACM International Collegiate Programming Contest

hide comments
2015-02-07 13:40:14 :D
Check test file below:
1 1
100

200 3
0 100 0

0 0

There are no cases where n > 1 and d == 1. Also, weights and results fit into 32b signed integer. Intermediate results should also fit.
2013-12-04 20:11:55 Derek Illchuk
Are there any tricky test cases?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.