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
Comments
  • #37: af commented 1 year, 3 months ago

    Reply
  • #41: yes commented 1 year, 3 months ago

    $$\\[100000000000em]$$

    Reply