题目描述

憨憨最近新装修了若干个教室，现在憨憨要负责给这若干个教室联通网络。

这若干个房间的标号可以默认是 $1$ ~ $n$ $(1\leq n\leq 10^6)$，要求每个房间都要被网络连接，不同房间安装网络的成本有所不同，在第 $i$ 个房间安装的成本为 $i$ 。为了节约成本，某些房间的网络可以使用 Wifi 信号覆盖，并且可以认为当在某个房间安装 Wifi 时，可以默认覆盖前后 $[i-k,i+k]$（包括 $i-k$ 和 $i+k$ 号房间）范围的所有房间。

现在给定一个由 0 和 1 组成的字符串，其中 $1$ 表示当前房间能安装 Wifi , $0$ 表示不能安装 Wifi，只能直接安装网络。请你帮憨憨计算出能让所有房间覆盖网络信号的最低成本。

输入格式

第一行输入两个参数 $n$ 和 $k\ (0<k\leq n\leq 10^6)$。

第二行是长度为 $n$ 的只有 0 和 1 组成的字符串。

输出格式

输出只有一行，即安装的最少费用。

5 2
00100

3

解释 #1

我们考虑在第三个位置安装 Wifi，即可联通所有房间的网络，所以成本为 $3$。

6 1
000000

21

解释 #2

因为没有位置可以安装 Wifi，所以必须要逐个安装网络，所以成本为 $1+2+3+4+5+6 = 21$。