你在宿舍里担任系统管理员,宿舍里沿着笔直的走廊有一个又一个的房间。房间编号从 $$$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$$$) — 房间数量和每个路由器的范围。
输入的第二行包含一个长度为 $$$n$$$ 的字符串 $$$s$$$,仅由零和一组成。如果字符串的第 $$$i$$$ 个字符等于“1”,则第 $$$i$$$ 个房间中有一个路由器位置。如果字符串的第 $$$i$$$ 个字符等于“0”,则不能将路由器放置在第 $$$i$$$ 个房间中。
输出
打印一个整数 — 将所有 $$$n$$$ 房间连接到互联网的最低总成本。
示例
输入 #1
5 2 00100
输出 #1
3
输入 #2
6 1 000000
输出 #2
21
输入 #3
4 1 0011
输出 #3
4
输入#4
12 6 000010000100
输出#4
15
注意
在第一个示例中,将路由器放置在房间 $$$3$$$ 中就足够了,然后所有房间都将连接到互联网。连接总成本为 $$$3$$$。
在第二个示例中,您可以将路由器放置在任何地方,因此您需要直接连接所有房间。因此,所有房间的总连接成本为 $$$1 + 2 + 3 + 4 + 5 + 6 = 21$$$。
在第三个示例中,您需要直接连接房间$$$1$$$,并将路由器放置在房间$$$3$$$中。因此,所有房间的总连接成本为 $$$1 + 3 = 4$$$。
在第四个示例中,您需要将路由器放置在 $$$5$$$ 和 $$$10$$$ 房间中。然后所有房间都将连接到互联网。连接总成本为 $$$5 + 10 = 15$$$。