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