Knapsack

You have a backpack that can carry a maximum weight of $C$. You will also be given a set of items, their weights and their values.

Determine the maximum total value of items that you can carry in your backpack.

Input

The input will start with two integers: $N$ ($1 \le N \le 10000$), the number of items, and $C$ ($1 \le C \le 10^6$) the capacity of your backpack.

The next $N$ lines will each contain a pair of integers: $W_i$ ($1 \le W_i \le 100$), the weight of item $i$, and $V_i$ ($1 \le V_i \le 100$) the value of item $i$.

Output

Print the maximum total value of items that you can carry in your backpack.

Sample

Input	Output
3 5 3 1 2 1 2 2	3
You can take the 2nd and the 3rd items. Their combined weight is 4 (less than the capacity, 5) and their total value is 3.