Knapsack

After many years of searching, you have finally found $$N$$ treasure conveniently labelled $$1$$ to $$N$$ buried on a deserted island. Each treasure $$i$$ has a weight $$W_i$$ and value $$V_i$$.

Unfortunately, you only brought with you one knapsack which can carry treasures with a weight sum no more than $$K$$.

Determine the maximum value of treasure you can carry.

Constraints

$$1\le N\le 100$$

$$1\le K\le 10^8$$

$$1\le Wi, Vi\le 10^8$$

Input Specification

The first line will contain $$N$$ and $$K$$ separated by a space.

The next $$N$$ lines each contain two space-separated integers. The $$i$$th line contains $$W_i$$ and $$V_i$$.

Output Specification

Output one integer, the maximum value of treasure you can carry.

Sample Input

3 5010 6020 10030 120

Sample Output

220
$$\\[100000000000em]$$