The below mentioned question appeared in one of the contest on binarysearch.io which is similar to leetcode for interview preparations.

I needed your help in explanation of the following question. I couldn't understand the editorial over there. I hope you guys can try it first on your own and then provide an explanation for it.

Here is the question:

You are given a string s containing "1"s and "0"s and an integer k. Return the minimum number of swaps required so that there's a group of k contiguous "1"s. Swaps must be adjacent.

Constraints

 n ≤ 100,000 where n is the length of s.

Example 1

Input

s = "10011"
k = 3

Output

2

Explanation
We can swap the first "1" right twice to have 3 contiguous "1"s.