Minimizing 1-Blocks by Deleting Zeros

You are given a binary string of length \(n\) consisting only of characters '0' and '1'. You are required to delete exactly \(k\) zeros from the string. A block is defined as the longest consecutive segment of identical digits. In other words, each maximal substring of consecutive 1's or consecutive 0's is considered a block.

Your goal is to choose which \(k\) zeros to delete so that the number of blocks of consecutive 1's in the final string is minimized. Note that when you delete a zero, the remaining parts of the string are concatenated. Therefore, if you remove all the zeros between two 1-blocks, these blocks merge into a single block.

More formally, suppose the original string has \(m\) blocks of consecutive 1's. For each gap (i.e. group of consecutive zeros) between two adjacent 1-blocks with length \(L\), if you remove all \(L\) zeros from that gap, the two 1-blocks merge into one. Your task is to choose which gaps to completely remove (using exactly \(k\) deletions overall) in order to minimize the final number of 1-blocks.

If there is no '1' in the string, the answer is \(0\).

inputFormat

The input consists of two lines:

1. The first line contains two integers \(n\) and \(k\) (\(1 \leq n \leq 10^5\), \(0 \leq k \leq \) number of zeros in the string), where \(n\) is the length of the binary string and \(k\) is the number of zeros to delete.
2. The second line contains a binary string of length \(n\) composed of characters '0' and '1'.

outputFormat

Output a single integer — the minimum number of blocks of consecutive '1's that can be achieved by deleting exactly \(k\) zeros optimally.

sample

3 1
101

1