Задачі
Двокольорові Коні
Двокольорові Коні
Кожного день фермер Іон (це румунське ім'я) виводить усіх своїх коней, щоб вони могли побігати і погратись. Коли вони нагуляються, фермер Іон заганяє їх назад у стійла. Для цього він спочатку розставляє їх усіх у лінію, а потім заводить у стійла. Так як коні достатотньо втомлені, фермер Іон вирішив, що вони не повинні рухатись більше, ніж можуть. Тому він розробив наступний алгоритм: перші \textbf{P_1} коней ставляться у перше стійло, наступні \textbf{P_2} у друге стійло і так далі. Він також не хоче, щоб довільне з його \textbf{K} стійл залишалось порожнім, і жоден з коней не повинен залишатись на вулиці. Вам також потрібно знати, що у фермера Іона є лише чорні та білі коні, які не дуже миряться одні з одними. Якщо в одному стійлі знаходяться \textbf{i }чорних та \textbf{j} білих коней, то коефіцієнт нещстя цього стійла дорівнює \textbf{i*j}. Загальний коефіцієнт нещастя дорівнює сумі коефіцієнтів нещастя для кожного з \textbf{K} стійл.
Визначте, як розмістити \textbf{N} коней у \textbf{K} стійл так, щоб загальний коефіцієнт нещастя був мінімальним.
\InputFile
Перший рядок містить \textbf{2} числа: \textbf{N }(\textbf{1 }≤ \textbf{N }≤ \textbf{500}) та \textbf{K} (\textbf{1} ≤ \textbf{K} ≤ \textbf{N}). У Наступних \textbf{N} рядках знаходиться \textbf{N} чисел. \textbf{i}-ий з цих рядків містить колір \textbf{i}-ого коня у послідовності: \textbf{1} означає що кінь чорний, \textbf{0} - що кінь білий.
\OutputFile
Вивести одне число - найменше можливе значення спільного коефіцієнта нещастя.
Вхідні дані #1
6 3 1 1 0 1 0 1
Вихідні дані #1
2