Gem Knapsack Optimization

You are given \(n\) gems. Each gem has a weight and a value. Your task is to select some of these gems such that the total weight does not exceed \(W\) and the total value is maximized. Output the maximum possible total value.

Note: Each gem can be chosen at most once.

inputFormat

The first line contains two integers \(n\) and \(W\) where \(n\) is the number of gems and \(W\) is the maximum allowed weight.

Then \(n\) lines follow, each containing two integers \(w_i\) and \(v_i\), representing the weight and value of the \(i\)-th gem, respectively.

outputFormat

Output a single integer, the maximum total value that can be achieved without exceeding the weight \(W\).

sample

3 5
2 3
1 2
3 4

7