XrkArul is on a straight line, he is now at position 1 and needs to go back to his home in N. He can flash to the right at a distance of no more than K, that means he can flash from point x as far as x + a.
For every point from 1 to N, if it is "1" then it is a portal, and vice versa.
XrkArul can only flash at portals. Make sure there are portals at points 1 and N.
Please help XrkArul calculate the minimum number of flashes needed to get from point 1 to point N. Let's say XrkArul starts at point 1. If XrkArul cannot reach home, output -1.
The first line contains two integers n and K(2≤n≤1000,1≤K≤ n-1) -the location of XrkArul's home, and the maximum length he can flash.
The second line contains a string s of length n, consisting of '0' and '1'. If a character in string S is equal to '0', then there is no portal at the corresponding point. In the other case, there is a portal at the corresponding point. Ensure that the first and last characters of string s are equal to '1'.
If XrkArul cannot reach home, print -1.
In the other case, print the minimum number of flashes required for XrkArul to get from point 1 to the home of point N.
8 4 11100101
3 Note:In this case,XrkArul can flash to position 3 ,then position 6 and then position 8 ,costs only 3 times.There's no better paln.