Your friend has just accused you of having good gacha luck. To prove them wrong, you have been keeping track of the results of every gacha pull over the past few months in a spreadsheet. Specifically, your spreadsheet contains $N$ entries, each containing a value of either a $0$ or a $1$. A value of $1$ in the $i$-th entry denotes that the $i$-th pull contained a 4 star card, and a $0$ denotes otherwise. The unluckiness score of a subsection (a contiguous subsequence) of these entries is calculated as follows:

1. The score is initially set to be the number of $0$s in the subsection.
2. Then, for each $1$ in the subsection, the unluckiness score is halved without rounding.
3. Finally, the score is set to be the smallest integer that is no smaller than its current value.

To refute their claim as effectively as possible, you will send them $K$ screenshots containing mutually disjoint subsections of your spreadsheet. What is the maximum possible total unluckiness score of the $K$ subsections in the screenshots?

Constraints

$1\le K\le N\le {10}^6$

Subtask 1 [1/15]

$K=1$

$1\le N\le 500$

Subtask 2 [1/15]

$K=1$

$1\le N\le 3\times {10}^3$

Subtask 3 [2/15]

$K=1$

Subtask 4 [5/15]

$1\le K\le N\le 500$

Subtask 5 [3/15]

$1\le K\le N\le 3\times {10}^3$

Subtask 6 [3/15]

No additional constraints.

Input Specification

The first line contains $2$ integers $N$ and $K$.

The second line contains a binary string of length $N$, representing the entries of the spreadsheet in order.

Output Specification

Output a single integer on its own line, the maximum possible total unluckiness score of the $K$ subsections.

Sample Input

9 2
001000100

Sample Output

5

Explanation

One optimal solution would be to include the first $6$ entries in the first screenshot and the $8$-th and $9$-th entries in the second. These have unluckiness scores of $3$ and $2$ respectively, giving a total unluckiness score of $5$.