SP17258 HPREFIX - Yungom

**Yungom** Dae Jang Guem（在波斯语中被称为 Yungom）在完成了关于「如何制作披萨」的烹饪学博士论文，以及在医学领域找到了艾滋病和阿尔茨海默病的治疗方法后，现在着手解决信息理论的一个新问题。这个问题连信息论之父 Shannon 都未能攻克。她计划用给定的 $d$ 个字符 $c_1, c_2, \ldots, c_d$ 构造一个由 $n$ 个词组成的语言。这个语言必须是前缀自由的，也就是说，不存在一个词是另一个词的前缀。 每个字符 $c_i$ 具有使用成本 $w_i$。一个长度为 $l$ 的词的成本就是它所包含的字符的成本之和。例如，如果 $c_1=a$ 且 $c_2=b$，同时 $w_1=1$ 和 $w_2=10$，则词 "aba" 的成本为 $1+10+1=12$。类似地，一个由 $n$ 个词构成的语言的总成本是所有词的成本之和。例如，语言 "ab"、"bbb" 和 "baaa" 的成本为 $11+30+13=54$。Yungom 希望完美解决这一任务，即找到使总成本最小的前缀自由语言。

输入包含多组测试数据。每组测试数据的第一行给出两个整数 $n$ 和 $d$ ($1 \le n, d \le 100$)。接下来的一行包含 $d$ 个整数 $w_1, w_2, \ldots, w_d$，每个整数表示一个字符的使用成本（$1 \le w_i \le 1000$）。 当输入为 $n = 0$ 且 $d = 0$ 时，表示输入结束。

对于每组测试数据，输出一个整数，代表构造含有 $n$ 个词的前缀自由语言的最小成本。

- $1 \le n, d \le 100$ - $1 \le w_i \le 1000$ **本翻译由 AI 自动生成**