Alyona 最近购买了一台微型冰箱,它可以表示为具有 $$$h$$$ 行和 $$$2$$$ 列的矩阵。最初,冰箱底部只有一个架子,但阿廖娜可以在冰箱内任意两排之间安装任意数量的架子。一个搁板有两个单元格宽,不占用任何空间,但将冰箱内部分隔为下部和上部。
一个带有 $$$h = 7$$$ 和两个架子的冰箱示例。架子显示为黑色。该图对应于第一个示例。
Alyona 有 $$$n$$$ 瓶牛奶,她想把它们放进冰箱。第 $$$i$$$ 个瓶子的高度为 $$$a_i$$$ 个单元格,宽度为 $$$1$$$ 个单元格。如果架子上方的相应空间至少与瓶子一样高,她可以将瓶子放在某个架子上。她不能将一个瓶子放在另一个瓶子上面(如果它们之间没有架子)。两个瓶子不能共用一个单元。
Alyona 对最大整数 $$$k$$$ 感兴趣,以便她可以同时将瓶子 $$$1$$$、$$$2$$$、...、$$$k$$$ 放入冰箱。找到这个最大的$$$k$$$。
输入
第一行包含两个整数 $$$n$$$ 和 $$$h$$$ ($$$1 \le n \le 10^3$$$, $$$1 \le h \le 10^9$$$) — 瓶子的数量和冰箱的高度。
第二行包含 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le h$$$) - 瓶子的高度。
输出
打印单个整数 $$$k$$$ — Alyona 可以同时将瓶子 $$$1$$$、$$$2$$$、...、$$$k$$$ 放入冰箱的最大整数。如果 Alyona 可以将所有瓶子放入冰箱,请打印 $$$n$$$。不难看出,Alyona 总是能在冰箱里至少放一瓶。
示例
输入 #1
5 7 2 3 5 4 1
输出 #1
3
输入 #2
10 10 9 1 1 1 1 1 1 1 1 1
输出 #2
4
输入 #3
5 10 3 1 4 2 4
输出 #3
5
注意
第一个示例中的最佳位置之一如声明中的图片所示。
第二个示例中的最佳位置之一如下图所示。
第三个示例中的最佳位置之一如下图所示。