题目描述

\(\text{Smart}\) 特别爱吃苹果。他家有两棵苹果树（编号为 \(1\) 和 \(2\)），每一棵树上都长满了苹果。\(\text{Smart}\) 无法摘下树上的苹果，所以他只能等待苹果从树上落下。但是，由于苹果掉到地上会摔烂，\(\text{Smart}\) 必须在半空中接住苹果（没有人爱吃摔烂的苹果）。

每一分钟，两棵苹果树其中的一棵会掉落一个苹果。\(\text{Smart}\) 已经过了足够的训练，只要站在树下就一定能接住这棵树上掉落的苹果。同时，\(\text{Smart}\) 能够在两棵树之间快速移动（移动时间远少于\(1\)分钟），因此当苹果掉落时，他必定站在两棵树其中的一棵下面。此外，\(\text{Smart}\) 不愿意不停地往返于两棵树之间，因此会错过一些苹果。

苹果每分钟掉落一个，共 \(T\) 分钟，\(\text{Smart}\) 最多愿意移动 \(W\) 次。现给出每分钟掉落苹果的树的编号，请求 \(\text{Smart}\) 能够接住的最多苹果数。

郑重告诉你：开始时 \(\text{Smart}\) 在1号苹果树下。

格式

输入格式

输入共 \(2\) 行：

第 \(1\) 行：由空格隔开的两个整数 \(T\) 和 \(W\)；

第 \(2 \sim T+1\) 行：第 \(i+1\) 行一个整数 \(1\) 或 \(2\)，表示第 \(i\) 分钟掉落苹果的树的编号。

输出格式

输出 \(1\) 行，包含一个整数，表示能接到的最多苹果数。

样例1

样例输入1

7 2
2
1
1
2
2
1
1

样例输出1

6

样例2

样例输入2

25 25
1
2
1
2
1
1
1
2
2
1
1
2
2
1
2
2
2
1
1
2
1
1
2
2
2

样例输出2

25

样例3

样例输入3

3 18
2
1
2

样例输出3

3

样例1解释

\(\text{Smart}\) 不移动直到接到从第 \(1\) 棵树上掉落的两个苹果，然后移动到第 \(2\) 棵树下，直到接到从第 \(2\) 棵树上掉落的两个苹果，最后移动到第 \(1\) 棵树下，接住最后两个从第 \(1\) 棵树上掉落的苹果。这样共接住\(6\) 个苹果。

限制

\(40\%\)的数据：\(T≤100，W≤30\)；

\(70\%\)的数据：\(T≤1000，W≤30\)；

\(100\%\)的数据：\(1≤T≤10000，1≤W≤100\)。