Moloco is an advertising technology company that helps various companies around the world improve their online advertising. Using Moloco's technology, internet users can see more relevant ads, and advertisers can advertise more effectively.

Jongseo predicted that a user will visit a homepage a total of $2N$ times, and he wants to show the user two types of ads, ad 0 and ad 1, $N$ times each. If the same type of ad appears repeatedly every time the homepage is visited, people may become accustomed to the ads, reducing their effectiveness. Therefore, he wants to maximize the advertising effect by arranging the two types of ads well.

To quantitatively measure the advertising effect, Moloco engineer Jongseo defined a metric called "boredom." For $i \leq j$, the boredom of a segment consisting of ads from the $i$-th to the $j$-th is defined as the absolute difference between the number of 0-type ads and 1-type ads within that segment. The boredom that the user ultimately feels is the maximum value of the boredom among all possible segments.

For example, if the ads are arranged in the order 00110110, the boredom of the segment from the $3$-rd ad to the $7$-th ad is $|1 - 4| = 3$. Since this segment has the highest boredom, the boredom the user ultimately feels is also $3$.

Through Moloco's excellent algorithms, an effective ad arrangement that can increase user engagement has been found. However, Jongseo wants to reduce the boredom to see how well the "boredom" metric works. Since the order of the ads is already fixed, he must spend a cost of $1$ to swap two adjacent ads to reduce the boredom. He can perform the swapping operation as many times as he wants.

What is the minimum cost required to make the boredom that the user ultimately feels $K$ or less?

Input

The first line contains $N$ and $K$ separated by a space. ($1 \le K \le N \le 500\,000$)

The second line contains a string of length $2N$ consisting only of $N$ 0s and $N$ 1s, representing the initial ad arrangement.

Output

Output the minimum cost required to make the boredom $K$ or less.

If the boredom of the given ad sequence is already $K$ or less, output 0.

It can be shown that it is always possible to make the boredom $1$ for all possible inputs. In other words, an answer always exists.

Examples

Input 1

4 2
00110110

Output 1

1

Input 2

4 2
11110000

Output 2

3

Input 3

4 1
10011001

Output 3

2