题目描述

奶牛喜欢苹果是一个鲜为人知的事实。 $\red{Farmer John }$在他的地里有两棵苹果树（方便地编号为 $\red{1 }$和 $\red{2}$），每棵都长满了苹果。当苹果在树上时，贝西 够不着苹果，所以她必须等它们掉下来。

然而，她必须在空中接住它们，因为苹果落地时会擦伤（而且没有人愿意吃擦伤的苹果）。贝西吃得很快，所以她抓到的苹果在几秒钟内 就被吃掉了。每分钟，两棵苹果树中的一棵会掉落一个苹果。

贝西经过多次练习，如果她站在一棵树下，她就可以接住一个苹果。虽然 $\red{Bessie }$可以在两棵树之间快速行 走（不到一分钟），但她任何时候都只能站在一棵树下。

而且，奶牛没有得到太多的运动，所以她不愿意无休止地在树间来回走动（因此错过了一些苹果）。苹果掉落（每分钟一 个）$\red{T (1 <= T <= 1,000) }$分钟。 $\red{Bessie }$最多愿意来回走 $\red{W (1 <= W <= 30) }$次。

给定哪棵树每分钟会掉落一个苹果，确定 $\red{Bessie }$可以抓 到的最大苹果数。 $\red{Bessie }$从树 $\red{1 }$开始。

输入格式

第 $\red{1 }$行：两个空格分隔的整数：$\red{T }$和 $\red{W}$

第 $\red{2...T+1 }$行：$\red{1 }$或 $\red{2：}$每分钟会掉落一个苹果的树。

输出格式

第 $\red{1 }$行：$\red{Bessie }$不走超过 $\red{W }$次就可以抓到的最大苹果数。

样例

输入样例

7 2
2
1
1
2
2
1
1

输出样例

6

提示

输入详细信息：

七个苹果从树$\red{2}$掉下来，一个从树$\red{1}$掉下来，然后一排两个从树上掉下来树$\red{2}$的两个一行，然后树$\red{1}$的两个。贝西是愿意从一棵树 走到另一棵树两次。

输出详细信息：

贝西可以在第一棵树下一直呆到前两棵，这样就可以摘到六个苹果下降，然后移动到树$\red{2}$进行下两个，然后返回到树$\red{1}$的最后两个。