eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Двухцветные лошади

Двухцветные лошади

Лимит времени 1 секунда
Лимит использования памяти 16 MiB

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

Определите, как расположить N лошадей в K стойл так, чтобы общий коэффициент несчастья был минимальным.

Входные данные

Первая строка содержит 2 числа: N (1 N 500) и K (1KN). На следующих N строках находится N чисел. i-ая из этих строк содержит цвет i-ой лошади в последовательности: 1 означает что лошадь черная, 0 - что лошадь белая.

Выходные данные

Вывести одно число - наименьшее возможное значение общего коэффициента несчастья.

Пример

Входные данные #1
6 3
1
1
0
1
0
1
Выходные данные #1
2
Автор Mugurel Ionut Andreica
Источник Romanian Open Contest, December 2001