← 返回题目列表

Codeforces · 1119/B

B. 阿廖娜和窄冰箱

中文机器翻译题面 查看原题

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

注意

第一个示例中的最佳位置之一如声明中的图片所示。

第二个示例中的最佳位置之一如下图所示。

第三个示例中的最佳位置之一如下图所示。