Problem D
Pulverizing Pancake

The Living Embodiment of Doom

You were walking along minding your own business when you were suddenly ambushed by a horde of wild Pokemon. The world is a grid with $N$ columns numbered from $1$ to $N$, and each Pokemon is in one of the columns hoping to trap you, but you have come prepared. You brought your trusty Snorlax who knows how to use one of the most powerful moves known to Pokemon-kind: Pulverizing Pancake. When it uses this move, Snorlax barrels down any one of the columns defeating any Pokemon in his path.

His impact is so large that Pokemon in adjacent columns get pushed into the column one over. For example, if Snorlax barrels down column $3$, Pokemon in column $3$ will be defeated, any Pokemon in column $2$ will be pushed into column $1$ (but not defeated), and any Pokemon in column $4$ will be pushed into column $5$. The pushing effect always happens unless the Pokemon getting pushed are on the first or last columns of the world (i.e. Snorlax barrels down column $2$ or column $N-1$), in which case the Pokemon in adjacent columns don’t move (since there is no column for them to be pushed to). The effect only occurs in the two adjacent columns to Snorlax; it is not a chain reaction across the entire grid.

Your Snorlax only has a limited number of uses of this powerful move, so you want to minimize the amount of times you use it while still defeating every Pokemon. For each use of the move, you may choose any column for Snorlax to barrel down (including columns with no Pokemon in it). Calculate how many times Snorlax must use Pulverizing Pancake to defeat all the wild Pokemon.

Input

The input starts with one line containing two space-separated integers $N$ and $M$. This denotes the number of columns in the world ($1 \leq N \leq 10^5$) and the number of columns with wild Pokemon in them ($0 \leq M \leq N$).

The second line contains a string $a_1a_2 \ldots a_ N$ of $N$ $1$s and $0$s, where $a_ i$ is $1$ if there are wild Pokemon in column $i$ and $0$ otherwise.

Output

Output a single line containing the minimum number of times Snorlax must use Pulverizing Pancake to defeat all wild Pokemon.

3 3
111

2

6 5
110111

4