暂无测试数据。

DD 现在有一个高度为 $m$，宽度为 $2$ 的储物柜，她现在有 $n$ 个蛋糕，其中第 $i$ 个的高度是 $h_i$ ，每个蛋糕的宽度均为 $1$ 。

因为 DD 不想吃被压扁的蛋糕，所以她要在储物柜里放任意数量的货架板（货架板本身的高度可以忽略），而且 DD 有一个特殊的习惯，就是一定是从第 $1$ 个蛋糕开始选择连续一段蛋糕，也就是如果 DD 放 $k$ 个蛋糕，一定是放第 $1 \sim k$ 个蛋糕。

那请问 DD 最多可以把前多少个蛋糕放到储物柜里

输入格式

第一行两个整数分别表示 $n,m$

第二行 $n$ 个整数,其中第 $i$ 个表示 $h_i$

输出格式

共一行，输出 DD 最多可以将前多少个蛋糕放在储物柜里

数据规模与约定

对于 $30\%$ 的数据，$1 \leq m \leq 20$

对于 $50\%$ 的数据，$1 \leq n \leq 20$

对于 $100\%$ 的数据，$1 \leq n \leq 1000,1 \leq h_i, m \leq 10^9$

3 4
2 4 6

2