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 \textbf{n} words with \textbf{d} given characters \textbf{c_1}, \textbf{c_2}, …, \textbf{c_d}. This language should be prefix free which means that there is no pair of words like \textbf{(s, t)} in which the word \textbf{s} is a prefix of \textbf{t}. Each character \textbf{c_i} has a usage cost of \textbf{w_i}. The cost of a word \textbf{s} with the length \textbf{l} is the sum of the costs of its \textbf{l} characters. For example, if \textbf{c_1=a}; \textbf{c_2=b}; \textbf{w_1=1 }and \textbf{w_2=10}, the cost of word "\textbf{aba}" is \textbf{1+10+1=12}. Similarly, the cost of a language with \textbf{n} words is equal to the sum of the costs of its \textbf{n} words. For example, the cost of language "\textbf{ab}"; "\textbf{bbb}"; "\textbf{baaa}" is \textbf{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 \textbf{n} words. \InputFile There are multiple test cases in the input. Each test case starts with a line containing two integers \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{200}) and \textbf{d} (\textbf{1} ≤ \textbf{d} ≤ \textbf{200}). The next line contains nonnegative integers \textbf{w_1}, \textbf{w_2}, …, \textbf{w_d}. The input is terminated by a line containing two zero numbers. \OutputFile For each test case, you should print the minimum cost of a prefix free language with \textbf{n} words and \textbf{d} characters.