Юнгом
После получения докторской степени по кулинарии с исследовательской работой на тему "Как приготовить пиццу" и еще одной докторской степени по медицине за нахождение лекарств от ВИЧ и болезни Альцгеймера, Дэ Чжан Гым (называемая Юнгом на персидском) решила взяться за решение еще одной нерешенной проблемы в теории информации, которую даже Шеннон (отец теории информации) не смог решить. Она планирует создать язык из 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 символов.