You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

熊大 正在玩一款有趣的电子游戏，游戏的目标是通过操作一系列开关来关闭所有亮着的指示灯。游戏的规则有些特殊，让熊大 感到有些棘手。

为了简化问题，游戏中有 n 个指示灯 排成一排，每个指示灯的状态可以用一个长度为 n 的字符串 s 表示。假设字符串编号从 1 开始，那么 s[i] = 0 表示第 i 个指示灯是关闭的，s[i] = 1 表示第 i 个指示灯是亮着的。

然而，游戏的开关系统存在一些限制：熊大 每次操作只能改变连续 k 个指示灯的状态（改变状态意味着亮着的灯会熄灭，熄灭的灯会亮起）。

现在，熊大 想要关闭所有的 n 个指示灯。请你帮他计算最少需要操作多少次。如果无法关闭所有指示灯，则输出 "so hard"（不包含引号）。

输入格式

第一行输入两个整数 n 和 k，分别表示指示灯的数量和每次操作可以改变状态的连续指示灯的数量。

第二行输入一个长度为 n 的字符串 s，只包含字符 0 和 1，表示指示灯的初始状态。

输出格式

如果可以关闭所有指示灯，输出一个整数，表示最少需要的操作次数；否则输出 "so hard"。

样例输入输出

5 2
01010

2

说明/提示

样例解释

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

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

数据范围

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

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