F. Wi-Fi
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы работаете администратором в общежитии, состоящем из $$$n$$$ комнат, расположенных в ряд вдоль коридора. Комнаты пронумерованы слева направо от $$$1$$$ до $$$n$$$.

Вы хотите подключить все $$$n$$$ комнат к интернету.

Каждая из комнат может быть подключена к интернету кабелем напрямую, стоимость подключения $$$i$$$-й комнаты равна $$$i$$$ монет.

В некоторых комнатах также есть место для установки роутера. Стоимость установки роутера в $$$i$$$-й комнате также равна $$$i$$$ монет. Вы не можете поставить роутер в комнате, в которой нет места для его установки. Когда вы ставите роутер в комнате $$$i$$$, вы подключаете все комнаты с номерами от $$$max(1,~i - k)$$$ до $$$min(n,~i + k)$$$ включительно к интернету, где $$$k$$$ — это радиус действия роутера. Значение $$$k$$$ одинаково для всех роутеров.

Определите минимальную стоимость подключения всех $$$n$$$ комнат к интернету. Считайте, что количество комнат, в которые можно установить роутеры, не превосходит количества роутеров, которые у вас есть.

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

В первой строке следуют два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n, k \le 2 \cdot 10^5$$$) — количество комнат и радиус действия каждого роутера.

Во второй строке следует строка $$$s$$$ длины $$$n$$$, состоящая только из нулей и единиц. Если $$$i$$$-й символ строки равен единице, то в $$$i$$$-й комнате есть место для установки роутера. Если $$$i$$$-й символ строки равен нулю, то в $$$i$$$-й комнате нет места для установки роутера.

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

Выведите одно целое число — минимальную стоимость подключения всех $$$n$$$ комнат к интернету.

Примеры
Входные данные
5 2
00100
Выходные данные
3
Входные данные
6 1
000000
Выходные данные
21
Входные данные
4 1
0011
Выходные данные
4
Входные данные
12 6
000010000100
Выходные данные
15
Примечание

В первом примере достаточно установить роутер в комнату $$$3$$$, тогда все комнаты будут подключены к интернету. Стоимость подключения равна $$$3$$$.

Во втором примере нельзя устанавливать роутеры ни в одну из комнат, поэтому все комнаты нужно подключать напрямую кабелем. Таким образом, стоимость подключения всех комнат равна $$$1 + 2 + 3 + 4 + 5 + 6 = 21$$$.

В третьем примере комнату $$$1$$$ нужно подключить напрямую кабелем, а в комнату $$$3$$$ установить роутер. Таким образом, стоимость подключения всех комнат равна $$$1 + 3 = 4$$$.

В четвертом примере нужно установить роутеры в комнаты $$$5$$$ и $$$10$$$. Тогда все комнаты будут подключены к интернету. Стоимость подключения равна $$$5 + 10 = 15$$$.