Unable to contain themselves, $10^{100}$ introverts decide to visit the newly constructed landmark -- The Great $1$-by-$N$ Grid of JSOI Kingdom.

It is an introvert's ultimate dream to stand on any one of the $N$ cells, conveniently numbered $1$ to $N$ from left to right. Yet, social norms and arbitrary restrictions prevent this fairytale ending from coming into fruition. They include:

• Loyalty: One cell per introvert. This means we can represent the state of the $1$-by-$N$ Grid with a binary string $S$ of length $N$, where the $i$-th character of $S$ is 1 if cell $i$ is occupied, and 0 if it is empty.
• Respect: Minimal intimacy - introverts must respect others' personal space. Two cells $i$ and $j$ are $K$-adjacent if $\vert i-j \vert \leq K$. A collision occurs when a pair of introverts stand on a pair of $K$-adjacent cells. An empty cell is called peaceful if occupying it creates no extra collisions.
• Care: If an introvert is to enter the Grid,
  • if all cells are occupied, this operation is invalid; otherwise,
  • if there is no peaceful cell, the introvert may occupy any empty cell; otherwise,
  • the introvert must be considerate by occupying a peaceful cell that allows the maximum number of introverts to enter the Grid afterwards without collisions.
  Formally, let $T_i$ represent the resulting state after the introvert occupies peaceful cell $i$. Let $f(T_i)$ denote the maximum number of introverts that can subsequently enter the Grid without causing any additional collisions. The introvert may occupy any peaceful cell $i$ such that $f(T_i)$ is maximal over all possible values of $f$.
• Singularity: In each second, one introvert may enter the Grid, or one introvert may leave the Grid (and their corresponding cell becomes empty).

The $1$-by-$N$ Grid is initially empty. Given the final state of the Grid, deduce the minimum number of seconds that could have elapsed.

Input

The first line contains two positive integers $N$ and $K$, indicating the size of the Grid and the threshold of peacefulness respectively.

The second line contains a binary string $S$ of length $N$, indicating the final state of the Grid.

Output

Output a single non-negative integer, indicating the minimum number of seconds that could have elapsed such that the given state is reached.
It can be proven that all states $S$ can be reached from the initial state within a finite number of moves.

Constraints

For all subtasks, $1 \le K \le N \le 10^6$, and $0 \le S_i \le 1$ for all $1 \le i \le N$.

Subtask 1 (12 points): $N$ is an odd integer and $K=1$.

Subtask 2 (14 points): $N \le 2000$ and $K=1$.

Subtask 3 (11 points): $K=1$.

Subtask 4 (13 points): $N \le 16$.

Subtask 5 (9 points): $N \le 200$.

Subtask 6 (9 points): $N \le 2000$.

Subtask 7 (12 points): $N \le 10^5$.

Subtask 8 (20 points): No additional constraints.