### PEG Test - Halloween 2014

## Problem A: Trick-or-Treat

Ben is going trick-or-treating this Halloween.

Ben only has `D` minutes of trick-or-treat time. He has planned out a list of `N` houses to visit. In order to attain the maximum amount of candy possible, he will need to spend time bartering with each household. He knows that the `i`-th house will require `t _{i}` minutes of bartering.

Because of his excellent athletic abilities, it will take Ben exactly 1 minute to move between any pair of houses.

Determine the maximum number of houses Ben can visit on Halloween night. Note that he can begin at any house and visit the houses in any order, but will only receive candy from a house at the end of the bartering period.

### Input Format

Line 1 of input contains two integers `N`, `D` (1 ≤ `N` ≤ 10000; 1 ≤ `D` ≤ 10^{8}).

Line 2 of input will have `N` space-separated integers – the time in minutes it takes to barter with the `i`-th house. (1 ≤ `t _{i}` ≤ 10000).

### Output Format

Output a single integer, the greatest number of houses Ben can receive candy from.

### Sample Input 1

4 12 4 2 5 4

### Sample Output 1

3

### Explanation 1

Ben can spend 4 minutes bartering at the first house, move to the second house in 1 minute, spend 2 minutes bartering with the second house, move to the fourth house in 1 minute, and spend 4 minutes bartering at the fourth house. This will take a total of 4 + 1 + 2 + 1 + 4 = 12 minutes.

### Sample Input 2

2 10 9 1

### Sample Output 2

1

### Explanation 2

Ben can spend 9 minutes collecting candy from the first house, but will not have enough time to move to the second house to barter.

All Submissions

Best Solutions

**Point Value:** 5

**Time Limit:** 2.00s

**Memory Limit:** 16M

**Added:** Nov 07, 2014

**Author:** frenzybenzy

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...