Light

Felicia was given a long string of fancy lanterns, but not all of them are on to light the night. Felicia felt bad about that and he wants to light up all the lanterns. There is a kind of magic switch which can change the states of k continuous lanterns. Once you choose k continuous lanterns and install a switch on them, the states of all k continuous lanterns can be changed together (on ->off or off ->on), but you cannot choose some ones be changed and some ones not be changed.
Felicia wants to buy as few switches as possible so that he can install them to turn on all the lanterns. Please notice that each switch must control exactly k continuous lanterns.

The input consists of multiple test cases. The first line of each case contains integers n(0 < n <= 100000), which is the length of that string of fancy lanterns, and k(0 <= k <= n), which is the number of continuous lanterns that a switch will control. The next line consists of a string of “01” with length n. “1” means that lantern is on and “0” means off. Your job is turn all the “0” to “1”.
The last test case is followed by a line containing two zeros.

If you cannot finish this job, output “-1” or you should output the minimum number switches that you should buy to turn on all the lanterns.

4 2
0000
4 2
1001
4 2
0110
4 2
0111
0 0

2
1
3
-1

momodi

HDOJ Monthly Contest – 2010.01.02