Задача 3. Типичная вечеринка с бассейнами

Автор:А. Саранцев, И. Ланцов, А. Лепёха   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Кирилл приехал с друзьями отдыхать на тропический курорт. Прибыв в отель, они увидели N бассейнов одинакового размера, которые были расположены в ряд. К сожалению, водой были наполнены лишь K бассейнов. Увидев бассейны, Кирилл решил во что бы то ни стало провести бассейную вечеринку.

Для бассейной вечеринки нужно, чтобы все бассейны с водой были расположены рядом друг с другом (между каждыми двумя наполненными бассейнами не должно быть бассейнов без воды). Чтобы достичь этого, друзья могут перелить воду из любого наполненного бассейна в любой из двух соседних, если соседний не наполнен. Какое минимальное количество переливаний воды из бассейна в бассейн Кириллу и друзьям понадобится сделать, чтобы все было готово к вечеринке?

Формат входных данных

Первая строка входных данных содержит целые числа N К, где N — общее количество бассейнов, K — количество бассейнов, наполненных водой.

Вторая строка входных данных содержит строку S, состоящую из N символов 0 и 1. Si = 1, если бассейн на позиции i наполнен, Si = 0 в противном случае.

Гарантируется, что S содержит ровно K единиц.

Формат выходных данных

Требуется вывести целое число — минимальное количество переливаний.

Ограничения

1 ≤ K ≤ N ≤ 1000000

Описание подзадач и системы оценивания

Решение оценивается пропорционально количеству успешно пройденных тестов.

ПодзадачаБаллы
1 ≤ N ≤ 10, 1 ≤ K ≤ 320
1 ≤ N ≤ 1000, 1 ≤ K ≤ 100030
1 ≤ N ≤ 1000000, 1 ≤ K ≤ 100000050

Примеры тестов

Стандартный вход Стандартный выход
1
10 3
0010001010
    
4
    
2
10 2
0000011000
    
0
    

0.113s 0.015s 13