T4 小 Z 的关灯问题

时间：0.5s

空间：256M

题目描述

小 Z 站在一排灯前。这些灯有的亮着，有的关着。小 Z 觉得这些灯太过闪眼睛，所以想把这些灯全部熄灭。

为了简化问题，现在总共有 $n$ 盏灯排成一排，我们用一个长度为 $n$ 的字符串 $s$ 表示这些灯的初始状态。假设字符串编号从 $1$ 开始，那么 $s_i=0$ 表示第 $i$ 盏灯刚开始是关着的，$s_i=1$ 表示第 $i$ 盏灯刚开始是开着的。

但是，现在由于控制灯光的电路存在一些问题，小 Z 一次操作只能更改连续 $k$ 盏灯的状态（更改状态表示本来亮着的灯会关闭，本来关闭的灯会打开）。

问，小 Z 想要关闭所有的 $n$ 盏灯，最少需要操作多少次。如果小 Z 无法全部关闭这些灯，则输出 "so hard"（不包含引号）。

输入格式

第一行输入两个整数 $n,k$ 分别表示灯的数量和小 Z 操作的连续灯的数量。

第二行输入一个长度为 $n$ 的只包含 $01$ 字符的字符串 $s$ 表示初始灯的情况。

输出格式

一行一个整数，表示答案。

样例输入输出

5 2
01010

2

说明/提示

样例解释

第一次操作选择 $[2,3]$ 区间，灯的状态变为 00110

第二次操作选择 $[3,4]$ 区间，灯的状态变为 00000。

数据范围

对于 $20\%$ 的数据，有 $1\le n, k \le 10$。

对于 $40\%$ 的数据，有 $1\le n \le 10^5, 1\le k \le 100$。

对于 $100\%$ 的数据，有 $1\le n, k \le 10^6$。