The people sitting around you are all talking panickedly to each other. Smth is drinking copious amounts of coffee, and mmmmmmmmmmmmmmmmmmmm has resorted to trying random things in Python. ohi's eyes are about 2 cm away from her computer screen, and wither_rose48 is crying under the table. It seems that the only person in the room that's relaxing is Colin, but that's beside the point.

You really tried, but animation with HSA Console has really stumped you, and now you're left with an unfinished MyCreation assignment due at the end of the period!

However, there's still some mandatory features that you still have left to implement; not implementing them will lose you marks!

You have ~N~ features that you still haven't implemented, and each feature has a mark value of ~X_i~ and takes ~Y_i~ minutes to implement.

What is the maximum amount of marks you can get with the ~T~ minutes you have left?

Constraints

~1 \leq N,T \leq 10^4~

~1 \leq X_i,Y_i \leq 100~

Subtask 1 [25%]

~1 \leq N \leq 50~

Subtask 2 [75%]

No further constraints.

Input Specifications

The first line will contain two space-separated integers, ~N~ and ~T~.

The next ~N~ lines will contain two space-separated integers, ~X_i,Y_i~.

Output Specifications

Output a single integer, ~M~, the maximum number of points you can get with a total time consumption sum of less than or equal to ~T~.

Sample Input 1

3 7
4 2
8 1
6 5

Sample Output 1

14

Sample Case 1 Explanation

By taking the 2nd and 3rd features to implement, you take 6 minutes to implement them to provide you with a mark value of 14 (oh goodness me you still failed the assignment horribly).

Sample Input 2

3 10
1 100
100 1
100 1

Sample Output 2

200

Sample Case 2 Explanation

By taking the 2nd and the 3rd features again, you take 2 minutes to implement and receive a mark value of 200. Surely no one's gonna notice that you have a 200% in MyCreation...