It's almost report card time, so of course everyone has started
programming like mad. There are only
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
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
is worth
points and he knows in advance that he can solve it in
hours
.
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 Specification
Line : The integers
and
.
The next lines: Line
contains the integers
and
.
Output Specification
Output the maximum amount of points your friend can get in at most
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 hours, and
problems to choose from. To
maximize his points, he should do problems
,
,
,
, and
,
giving him
points in
hours.
Comments