Alyona and a Narrow Fridge

1000ms

262144K

Description:

Alyona has recently bought a miniature fridge that can be represented as a matrix with $$$h$$$ rows and $$$2$$$ columns. Initially there is only one shelf at the bottom of the fridge, but Alyona can install arbitrary number of shelves inside the fridge between any two rows. A shelf is two cells wide, does not occupy any space but separates the inside of the fridge to the lower and upper part.

$\text{[math]}$ An example of a fridge with $$$h = 7$$$ and two shelves. The shelves are shown in black. The picture corresponds to the first example.

Alyona has $$$n$$$ bottles of milk that she wants to put in the fridge. The $$$i$$$-th bottle is $$$a_i$$$ cells tall and $$$1$$$ cell wide. She can put a bottle on some shelf if the corresponding space above the shelf is at least as tall as the bottle. She can not put a bottle on top of another bottle (if there is no shelf between them). Two bottles can not share a cell.

Alyona is interested in the largest integer $$$k$$$ such that she can put bottles $$$1$$$, $$$2$$$, ..., $$$k$$$ in the fridge at the same time. Find this largest $$$k$$$.

Input:

The first line contains two integers $$$n$$$ and $$$h$$$ ($$$1 \le n \le 10^3$$$, $$$1 \le h \le 10^9$$$) — the number of bottles and the height of the fridge.

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le h$$$) — the heights of the bottles.

Output:

Print the single integer $$$k$$$ — the maximum integer such that Alyona can put the bottles $$$1$$$, $$$2$$$, ..., $$$k$$$ in the fridge at the same time. If Alyona can put all bottles in the fridge, print $$$n$$$. It is easy to see that Alyona can always put at least one bottle in the fridge.

Sample Input:

5 7
2 3 5 4 1

Sample Output:

Sample Input:

10 10
9 1 1 1 1 1 1 1 1 1

Sample Output:

Sample Input:

5 10
3 1 4 2 4

Sample Output:

Note:

One of optimal locations in the first example is shown on the picture in the statement.

One of optimal locations in the second example is shown on the picture below.

$\text{[math]}$

One of optimal locations in the third example is shown on the picture below.

$\text{[math]}$

Informação

Provedor Codeforces

Código CF1119B