Knapsack Value

Statement

You have n items. Item i has a weight and a value. You can carry total weight at most W. Each item can be taken at most once. What is the largest total value you can carry?

Input

The first line has n and W. Each of the next n lines has the weight and value of one item.

Output

Print one integer: the largest total value.

Constraints

1 <= n <= 100
0 <= W <= 10000
1 <= weight <= 10000
1 <= value <= 10^9

Example 1

4 7
1 1
3 4
4 5
5 7

9

Take the items of weight 3 and 4: value 4 + 5 = 9, total weight 7.

Example 2

1 4
5 10

0

The only item does not fit.