题目描述

你在宿舍担任系统管理员，走廊上有 $n$ 个房间依次排列。房间编号从 $1$ 到 $n$。

你需要将所有 $n$ 个房间连接到互联网。

你可以使用网线直接将每个房间连接到互联网，使用网线连接第 $i$ 个房间的成本为 $i$ 个硬币。

一些房间还预留有装路由器的支架。在第 $i$ 个房间放置路由器的成本也是 $i$ 个硬币。你不能在没有装路由器的支架的房间放置路由器。当你在第 $i$ 个房间放置路由器时，你将编号从 $max(1, i-k)$ 到 $min(n,i+k)$ 的所有房间连接到互联网，其中$k$是路由器的Wi-Fi覆盖范围。所有路由器对应的值 $k$ 相同。

计算将所有 $n$ 个房间连接到互联网的最小总成本。

你可以假设有路由器位置的房间数量不超过你拥有的路由器数量（即你拥有足够多的路由器）。

输入格式

输入的第一行包含两个整数 $n$ 和 $k$（$1 \le n, k \le 2 \cdot 10^5$），表示房间数量和每个路由器的范围。

输入的第二行包含一个长度为 $n$ 的字符串 $s$，只包含 0 和 1。如果字符串的第 $i$ 个字符等于 1，则第 $i$ 个房间有装路由器的支架。如果字符串的第 $i$ 个字符等于 0，则第 $i$ 个房间没有装路由器的支架，无法放置路由器。

输出格式

输出一个整数，表示将所有 $n$ 个房间连接到互联网的最小总成本。

样例

5 2
00100

3

6 1
000000

21

4 1
0011

4

12 6
000010000100

15