Лоуренс Аравийский
Т. Э. Лоуренс был противоречивой фигурой во время Первой мировой войны. Он служил британским офицером на Аравийском фронте и возглавлял группу арабских националистов в партизанских атаках против Османской империи. Основной его целью были железные дороги. Высоко вымышленная версия его подвигов была представлена в фильме "Лоуренс Аравийский".
Вам нужно создать программу, которая поможет Лоуренсу оптимально использовать свои ограниченные ресурсы. У вас есть информация от британской разведки. Во-первых, железнодорожная линия полностью линейна — без ответвлений и отводов. Британская разведка присвоила каждому депо стратегическую важность — целое число от 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, которую не следует обрабатывать.
Выходные данные
Для каждого набора данных выведите одно целое число, указывающее наименьшую стратегическую ценность для железной дороги, которую Лоуренс может достичь с помощью своих атак. Выведите каждое число в отдельной строке.