Minimum-Cost Prefix-Free Language

You must build a language of $n$ words over an alphabet of $d$ characters $c_1, c_2, \ldots, c_d$. The language must be prefix-free: no word may be a prefix of another, i.e. there is no pair of words $(s, t)$ in which $s$ is a prefix of $t$.

Each character $c_i$ has a usage cost $w_i$. The cost of a word equals the sum of the costs of its characters. For example, if $c_1 = a$, $c_2 = b$, $w_1 = 1$, and $w_2 = 10$, then the cost of the word aba is $1 + 10 + 1 = 12$.

The cost of a language equals the sum of the costs of all its words. For example, the language ab, bbb, baaa costs $11 + 30 + 13 = 54$.

Among all prefix-free languages that contain exactly $n$ words, find the minimum possible total cost.

When $n = 1$, the single word may be the empty word, whose cost is $0$.

The input contains several test cases. Each test case begins with a line holding two integers $n$ and $d$ ($1 \le n \le 200$, $1 \le d \le 200$). The next line holds $d$ nonnegative integers $w_1, w_2, \ldots, w_d$. The input ends with a line containing two zeros, which is not a test case.

For each test case, output a single line with the minimum cost of a prefix-free language of $n$ words built from the given $d$ characters.