一只青蛙生活在 Ox 轴上,需要到达位于 n 点的家。她从点1开始。青蛙可以向右跳,距离不超过d。所以,从 x 点跳起后,她可以到达 x + a 点,其中 a 是从 1 到 d 的整数。
对于从 1 到 n 的每个点,已知其中是否有一朵百合花。青蛙只能在百合花的点上跳跃。保证第1点和第n点有百合花。
确定青蛙从点1到达n点所需的最小跳跃次数。考虑青蛙最初位于点1。如果青蛙不能到达家,则打印-1。
输入
第一行包含两个整数 n 和 d (2 ≤ n ≤ 100, 1 ≤ d ≤ n - 1) — 青蛙想要到达的点,以及青蛙跳跃的最大长度。
第二行包含长度为 n 的字符串 s,由 0 和 1 组成。如果字符串s的某个字符等于0,则对应的点上没有百合花。在另一种情况下,在相应的点上有一朵百合花。保证字符串 s 的第一个和最后一个字符等于 1。
输出
如果青蛙无法到达家,则打印-1。
在另一种情况下,打印青蛙从点 1 到达点 n 的家所需的最少跳跃次数。
示例
输入 #1
8 4 10010101
输出 #1
2
输入 #2
4 2 1001
输出 #2
-1
输入 #3
8 4 11100101
输出 #3
3
输入#4
12 3 101111100101
输出#4
4
注意
在第一个示例中,from 可以通过两次跳转到达 home:第一次跳转从点 1 到点 4(跳转长度为 3),第二次跳转从点 4 到点 8(跳转长度为 4)。
在第二个示例中,青蛙无法到达家,因为要到达家,她需要跳三距离,但她跳跃的最大长度等于二。