Apple Catching

Farmer John's orchard has two apple trees numbered $1$ and $2$. Both trees are laden with apples. The cow, Bessie, loves apples but she is unable to pluck them from the trees. Instead, she must catch the apples in mid-air as they fall. However, if an apple hits the ground it becomes bruised, and nobody likes bruised apples.

Every minute, an apple falls from one of the two trees. Bessie is well‐trained such that if she stands under the tree from which the apple falls, she will catch it. Initially, Bessie stands under tree $1$. Although she can move quickly between the two trees (in much less than one minute), she is reluctant to move too frequently. Thus, over a period of $T$ minutes, she is willing to move at most $W$ times between the two trees.

You are given the sequence of trees from which the apples fall over $T$ minutes. Determine the maximum number of apples Bessie can catch.

inputFormat

The first line contains two integers $T$ and $W$ ($1 \le T \le 1000$, $1 \le W \le 30$), representing the number of minutes and the maximum number of moves allowed, respectively.

The next $T$ lines each contain an integer (either $1$ or $2$), where the $i$-th integer denotes the tree from which the apple falls at minute $i$.

outputFormat

Output a single integer representing the maximum number of apples Bessie can catch.

sample

7 2
2
1
1
2
2
1
1

6