Minimum Jumps to Cross the River

You are given a river represented by a string \(S\) of length \(n\), where each character corresponds to a position along the river. A character '0' indicates that there is a stone present at that position, and a '1' indicates water where you cannot land.

You start at the beginning of the river (position 0) and must reach the opposite bank at position \(n-1\) by jumping between stones. In each jump, you may move forward by at most \(d\) positions. Your task is to find the minimum number of jumps required to reach the end of the river. If it is impossible to cross the river following these rules, output \(-1\).

This problem can be modeled as a graph traversal where every stone (position with a '0') is a node. An edge exists from node \(i\) to node \(j\) if \(i < j \leq i+d\) and \(S[j]='0'\). The objective is to determine the shortest path from position 0 to position \(n-1\).

inputFormat

Input is read from standard input (stdin). The first line contains two integers (n) and (d) separated by a space. The second line contains a string (S) consisting solely of the characters '0' and '1'.

outputFormat

Output the minimum number of jumps required to cross the river. If it is impossible to cross the river, output (-1). The result should be written to standard output (stdout).## sample

5 3
00100

2