题目描述

鲜为人知的是，奶牛喜欢吃苹果。农夫约翰的田地里有两棵苹果树（方便起见编号为 1 和 2），每棵树上都结满了苹果。贝西够不到树上的苹果，所以她必须等苹果掉下来。不过，她必须在空中接住苹果，因为苹果掉到地上会碰伤（没人想吃碰伤的苹果）。贝西吃得很快，所以她接住的苹果几秒钟内就会被吃掉。

每分钟，两棵苹果树中的一棵会掉下一个苹果。贝西经过多次练习，如果她站在掉苹果的那棵树下，就能接住苹果。虽然贝西能在两棵树之间快速移动（用时远少于一分钟），但她任何时候只能站在一棵树下。此外，奶牛运动量不大，所以她不愿意在两棵树之间无休止地来回走动（因此会错过一些苹果）。

苹果会掉落 $T$（$1 \leq T \leq 1000$）分钟。贝西最多愿意来回走动 $W$（$1 \leq W \leq 30$）次。已知每分钟哪棵树会掉苹果，确定贝西最多能接住多少个苹果。贝西一开始站在 1 号树下。

输入

第 1 行：两个用空格分隔的整数 $T$ 和 $W$。

第 2 到 $T + 1$ 行：1 或 2，表示每分钟哪棵树会掉苹果。

输出

第 1 行：贝西在走动不超过 $W$ 次的情况下最多能接住的苹果数。

7 2
2
1
1
2
2
1
1

6

提示

输入详情： 一共掉落 7 个苹果，先是 2 号树掉一个，接着 1 号树连续掉两个，然后 2 号树连续掉两个，最后 1 号树连续掉两个。贝西最多愿意在两棵树之间走动两次。

输出详情： 贝西可以先待在 1 号树下接住前两个苹果，然后移动到 2 号树下接住接下来的两个苹果，最后回到 1 号树下接住最后两个苹果，这样一共能接住 6 个苹果。

来源

USACO 2004 年 11 月