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 50
10 60
20 100
30 120

Sample Output

220