Description

You are given a binary string of length $n$.

Define a block as the maximal substring of identical bits. For example, 0011101 has four blocks: 00, 111, 0, and 1.

You need to determine the minimum possible number of blocks of consecutive 1's after removing exactly $k$ 0's from the string.

Input Format

The first line contains two integers $n,k$.

The second line contains a binary string of length $n$.

Output Format

A single integer represents the minimum number of blocks of 1's.

8 2
10100101

2

16 5
0100100010100100

2

Hint

Sample Explanation #1

Remove the 0's located at $2$ and $7$.

Constraints

This problem uses subtasks.

• Subtask 0 (30 pts): $n\leq10^4$.
• Subtask 1 (30 pts): $e\leq10$.
• Subtask 2 (40 pts): no additional constraints.

$e$ denotes the number of 0's in the binary string.

For all test cases, it is guaranteed that $1\leq k\leq e\leq n\leq10^7$.