Background

Within my heart there lies a shadowed nook,

The realm of night, my birthright and my home.

Like myriad souls who through the twilight roam,

We'll reach those pristine shores we long mistook—

Where even darkness holds no fright, but brook.

Problem 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$.