Лоуренс Аравійський
T. Е. Лоуренс був суперечливою фігурою під час Першої світової війни. Він був британським офіцером, який служив на Аравійському фронті і очолював групу арабських націоналістів у партизанських атаках проти Османської імперії. Його основними цілями були залізниці. Дуже вигадана версія його подвигів була представлена у фільмі "Лоуренс Аравійський".
Вам потрібно створити програму, яка допоможе Лоуренсу визначити, як найкраще використати свої обмежені ресурси. У вас є певна інформація від британської розвідки. По-перше, залізнична лінія є повністю лінійною - немає відгалужень чи відростків. Далі, британська розвідка призначила Стратегічну Важливість кожному депо - ціле число від 1 до 5. Депо не має цінності саме по собі, воно має цінність лише якщо з'єднане з іншими депо. Стратегічна Цінність всієї залізниці обчислюється шляхом додавання добутків Стратегічних Цінностей для кожної пари депо, які з'єднані, прямо чи опосередковано, залізничною лінією. Розглянемо цю залізницю:
Її Стратегічна Цінність становить 4*5 + 4*1 + 4*2 + 5*1 + 5*2 + 1*2 = 49.
Тепер, припустимо, що у Лоуренса є ресурси лише для однієї атаки. Він не може атакувати самі депо - вони занадто добре захищені. Він повинен атакувати залізничну лінію між депо, посеред пустелі. Розглянемо, що станеться, якщо Лоуренс атакує цю залізничну лінію прямо посередині:
Стратегічна Цінність залишкової залізниці становить 4*5 + 1*2 = 22. Але, припустимо, Лоуренс атакує між депо 4 і 5:
Стратегічна Цінність залишкової залізниці становить 5*1 + 5*2 + 1*2 = 17. Це найкращий варіант для Лоуренса.
Маючи опис залізниці та кількість атак, які Лоуренс може здійснити, визначте найменшу Стратегічну Цінність, яку він може досягти для цієї залізниці.
Вхідні дані
Буде кілька наборів даних. Кожен набір даних починається з рядка з двома цілими числами, n та m. n - це кількість депо на залізниці (1 ≤ n ≤ 1000), а m - це кількість атак, на які у Лоуренса є ресурси (0 ≤ m < n). У наступному рядку буде n цілих чисел, кожне від 1 до 5, що вказує на Стратегічну Цінність кожного депо в порядку. Кінець введення буде позначено рядком з n=0 та m=0, який не слід обробляти.
Вихідні дані
Для кожного набору даних виведіть одне ціле число, яке вказує на найменшу Стратегічну Цінність для залізниці, яку Лоуренс може досягти своїми атаками. Виведіть кожне число в окремому рядку.