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.
\(1\le N\le 100\)
\(1\le K\le 10^8\)
\(1\le Wi, Vi\le 10^8\)
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 one integer, the maximum value of treasure you can carry.
3 50
10 60
20 100
30 120
220