## Coding Spree

It's almost report card time, so of course everyone has started programming like mad. There are only `T` (1 ≤ `T` ≤ 1000) hours left before the Sunday midnight deadline!

Luckily, you've earned your points gradually, so now you can just sit back and watch your classmates struggle. One of your friends in particular is really screwed, so he's decided to skip school all week and go on a coding spree.

Though your friend is lazy, he has done some problems on the Judge, so now he has exactly `N` (1 ≤ `N` ≤ 1000) problems available to him. No more problems will be posted until after the deadline, and he can't get partial marks on any of these problems. Problem `i` is worth `V _{i}` points and he knows in advance that he can solve it in

`H`hours (1 ≤

_{i}`V`,

_{i}`H`≤ 1000).

_{i}You're not a very pleasant person, so you want to torture your friend a bit. You plan to calculate the most points your friend could possibly get by the deadline, just so you can taunt him with that number.

### Input

Line 1: | The integers N and T |

The next N lines: |
Line i+1 contains the integers V and _{i}H_{i} |

### Output

Output the maximum amount of points your friend can get in at most `T` hours of coding.

### Sample Input

8 48 10 7 5 1 50 30 5 1 10 5 100 1000 25 10 60 40

### Sample Output

95

### Explanation

Your friend only has 48 hours, and 8 problems to choose from. To maximize his points, he should do problems 2, 3, 4, 5, and 7, giving him 95 points in 47 hours.

All Submissions

Best Solutions

**Point Value:** 10 (partial)

**Time Limit:** 1.00s

**Memory Limit:** 16M

**Added:** Jan 05, 2009

**Author:** SourSpinach

**Languages Allowed:**

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

## Comments (Search)

ChristerNilssonon Aug 12, 2014 - 11:22:16 am UTC Test case #5 seems to be missing the 20th pair of data.awaykenedon Aug 12, 2014 - 12:47:15 pm UTC Re: Test case #5 seems to be missing the 20th pair of data.xiaowuc1on Aug 12, 2014 - 4:21:45 pm UTC Re: Test case #5 seems to be missing the 20th pair of data.ChristerNilssonon Aug 12, 2014 - 9:16:32 pm UTC Re: Test case #5 seems to be missing the 20th pair of data.dr3won Sep 28, 2009 - 7:55:50 pm UTC *sigh*javicon Oct 25, 2009 - 3:11:58 am UTC Re: *sigh*javicon Oct 25, 2009 - 3:13:16 am UTC Re: Re: *sigh*bbi5291on Oct 25, 2009 - 3:39:28 am UTC Re: Re: *sigh*javicon Nov 07, 2009 - 1:03:19 am UTC Re: Re: *sigh*SourSpinachon Feb 09, 2009 - 2:46:56 am UTC HintThink of breaking this down into the subproblem "what's the maximum number of points I can get in X hours, using some set of the first Y problems".