You found ~N~ pieces of gold ore in a cave, each of which has weight ~w_i~ kg, and value ~v_i~. Since you are not that strong, you can only bring back ~W~ kg of gold ore. You want to maximize the sum of the values of the pieces of gold ore you bring back up. What is the maximum possible sum?

Input Specification

The first line will contain two integers ~N, W~ ~(1 \le N, W \le 1~ ~000)~.

The next ~N~ lines will each contain two integers, ~w_i, v_i~ ~(1 \le w_i, v_i \le 1~ ~000)~.

Output Specification

Output the maximum possible sum of the value of the pieces of gold ore you bring back to the surface.

Sample Input 1

3 3
1 1
2 2
3 4

Sample Output 1

4

Sample Input 2

3 11
11 10
5 3
6 6

Sample Output 2

10