Question
Queen Zerona's Bead Challenge
In a faraway land, there’s a kingdom where everything is either white or black, just like binary numbers. The Queen, Zerona, loves the white spaces, while the King, Onix, prefers the black dots.
One day, the Royal Mathemagician brings a long ribbon of N beads, arranged in a binary pattern of whites (0s) and blacks (1s). The Queen, curious about her influence, gives a task to her court:
"Find me all the sections of the ribbon, each K beads long, where my whites are equal to or outnumber King Onix’s blacks. I want to know how many such sections there are."
Can you help the court fulfill the Queen’s request?
One day, the Royal Mathemagician brings a long ribbon of N beads, arranged in a binary pattern of whites (0s) and blacks (1s). The Queen, curious about her influence, gives a task to her court:
"Find me all the sections of the ribbon, each K beads long, where my whites are equal to or outnumber King Onix’s blacks. I want to know how many such sections there are."
Can you help the court fulfill the Queen’s request?
Input
The first line of the input contains two integers N and K, the length of the binary string and the length of the substrings to test.
The second line of the input contains the binary string.
Constraints
1 ≤ K ≤ N ≤ 200000
Each character of the string is either 0 or 1.
The second line of the input contains the binary string.
Constraints
1 ≤ K ≤ N ≤ 200000
Each character of the string is either 0 or 1.
Output
Output a single integer, the answer to the problem.
Example
Sample Input
5 3
01010
Sample Output
2
Explanation
The substrings of length 3 are "010", "101", "010". Of these, the first and the third ones satisfy the condition.
5 3
01010
Sample Output
2
Explanation
The substrings of length 3 are "010", "101", "010". Of these, the first and the third ones satisfy the condition.