Юнгом#6909

Юнгом

1 секунда

64 мегабайти

Дуже легка

Після здобуття ступеня доктора філософії в кулінарії з дослідницькою роботою "Як приготувати піцу" та ще одного ступеня доктора філософії в медицині за знаходження ліків від ВІЛ та Альцгеймера, Де Чан Гем (яку перською називають Юнгом) вирішила взятися за ще одну нерозв'язану проблему в теорії інформації, яку навіть Шеннон (батько теорії інформації) не зміг вирішити. Вона планує створити мову з $n$ слів, використовуючи $d$ заданих символів $c_{1}$ c_1, $c_{2}$ c_2, …, $c_{d}$ c_d. Ця мова повинна бути префіксно-вільною, тобто не повинно існувати пари слів $(s, t)$ , де слово $s$ є префіксом слова $t$ . Кожен символ $c_{i}$ c_i має вартість використання $w_{i}$ w_i. Вартість слова $s$ з довжиною $l$ визначається як сума вартостей його $l$ символів. Наприклад, якщо $c_{1} = a$ c_1 = a; $c_{2} = b$ c_2 = b; $w_{1} = 1$ w_1 = 1 і $w_{2} = 10$ w_2 = 10, то вартість слова " $aba$ " дорівнює $1 + 10 + 1 = 12$ 1+10+1=12. Аналогічно, вартість мови з $n$ слів дорівнює сумі вартостей її $n$ слів. Наприклад, вартість мови " $ab$ "; " $bbb$ "; " $baaa$ " дорівнює $11 + 30 + 13 = 54$ 11+30+13=54.

Як і в попередніх завданнях, Юнгом прагне виконати це завдання ідеально, тобто вона хоче знайти мінімальну вартість префіксно-вільної мови з $n$ слів.

Вхідні дані

Вхідні дані містять кілька тестових випадків. Кожен тестовий випадок починається з рядка, що містить два цілі числа $n$ ( $1 \leq n \leq 200$ 1 \le n \le 200) і $d$ ( $1 \leq d \leq 200$ 1 \le d \le 200). Наступний рядок містить невід'ємні цілі числа $w_{1}$ w_1, $w_{2}$ w_2, …, $w_{d}$ w_d. Вхідні дані завершуються рядком, що містить два нулі.

Вихідні дані

Для кожного тестового випадку ви повинні вивести мінімальну вартість префіксно-вільної мови з $n$ слів і $d$ символів.

Приклади

Приклад 1