You are given a row of slots numbered from to . Each slot can either be vacant (`0`

) or contain a magnetic marble (`1`

). The magnetic forces in these marbles prompt adjacent ones to merge into a single marble, settling in the slot of the rightmost merging marbles. Marbles merge immediately when adjacent, including in the starting configuration. Your task is to place **exactly** marbles such that the resulting number of marbles is the minimum possible.

#### Input Specification

The input will consist of two lines. The first line will contain two integers and , representing the number of slots and number of marbles that you can add respectively.

The second line will contain a string of `0`

and `1`

of length .

The following table shows how the available marks are distributed.

Marks Awarded | ||
---|---|---|

marks | ||

marks |

#### Output Specification

The output will consist of a single integer indicating the minimum possible number of marbles in the slots after all marbles have been placed.

#### Sample Input 1

```
6 1
010111
```

#### Sample Output 1

`2`

#### Explanation for Sample 1

In the given example, the row of slots can be represented as `010111`

at the beginning. We can perform a merge immediately, and the configuration becomes `010001`

. We can place one marble at the first slot and result in the configuration `110001`

. Then, another merge can be performed, and our final configuration becomes `010001`

which has the minimum possible number of marbles after all marbles are placed and merged.

#### Sample Input 2

```
30 9
100010000000001001001000001001
```

#### Sample Output 2

`3`

## Comments

Can someone take a look at my submission. I keep getting WA for the 3rd test case. Thanks

can someone explain case sanple 2?

30 9

100010000000001001001000001001

(9 marbles remaining you have to add)it is optimal to first use 2 marbles here

100010000000001

001001000001001Now: 10001000000000

1111001000001001 -- > 100010000000000001001000001001(7 marbles remaining)it is optimal to then use 2 marbles here

100010000000000001001000001

001Now: 10001000000000000100100000

1111-- > 100010000000000001001000000001(5 marbles remaining)it is optimal to then use 2 marbles here

100010000000000001

001000000001Now: 10001000000000000

1111000000001 -- > 100010000000000000001000000001(3 marbles remaining)Finally, use 3 marbles here

1

00010000000000000001000000001Now:

111110000000000000001000000001 -- >000010000000000000001000000001there are 3 marbles left in the slots at the end. the order of the operations could have been switched but hope this helps

It is a bit hard to understand the example when you haven't put in the merging of the marbles into the explanation. But thank you so much, helped a lot!