Двухцветные лошади
Каждый день фермер Ион (это румынское имя) выводит всех своих лошадей, чтобы они могли побегать и поиграть. Когда они нагуляются, фермер Ион загоняет их обратно в стойла. Для этого он сначала расставляет их всех в линию, а потом заводит в стойла. Так как кони достаточно уставшие, фермер Ион решил, что они не должны двигаться больше, чем могут. Поэтому он разработал следующий алгоритм: первые P_1 лошадей ставится в первое стойло, следующие P_2 во второе стойло и так далее. Он также не хочет, чтобы любое из его K стойл оставалось пустым, и ни одна из лошадей не должна остаться на улице. Вам также следует знать, что у фермера Иона имеются только черные и белые лошади, которые не очень ладят друг с другом. Если в одном стойле находятся i черных и j белых лошадей, то коэффициент несчастья этого стойла равен i*j. Общий коэффициент несчастья равен сумме коэффициентов несчастья для каждого из K стойл.
Определите, как расположить N лошадей в K стойл так, чтобы общий коэффициент несчастья был минимальным.
Входные данные
Первая строка содержит 2 числа: N (1 ≤ N ≤ 500) и K (1 ≤ K ≤ N). На следующих N строках находится N чисел. i-ая из этих строк содержит цвет i-ой лошади в последовательности: 1 означает что лошадь черная, 0 - что лошадь белая.
Выходные данные
Вывести одно число - наименьшее возможное значение общего коэффициента несчастья.