Maximum Total Value Knapsack

You are given M items, where each item has a weight and a value. You also have a knapsack with a weight capacity W. Your task is to determine the maximum total value that can be obtained by selecting a subset of the items, such that the total weight does not exceed W. Each item can be chosen at most once.

You can solve this problem using dynamic programming. The recurrence relation is given by the following formula in LaTeX format:

\(dp[i][w] = \max\bigl(dp[i-1][w],\, dp[i-1][w - w_i] + v_i\bigr)\) for \(w_i \le w\),

with the boundary conditions \(dp[0][w] = 0\) for all \(w\), where \(w_i\) and \(v_i\) denote the weight and value of the \(i\)-th item, respectively.

inputFormat

The input is given via standard input (stdin). The first line contains two integers M and W, representing the number of items and the weight capacity of the knapsack, respectively. Each of the following M lines contains two space-separated integers, the first being the weight of an item and the second being its value.

outputFormat

Output a single integer via standard output (stdout): the maximum total value that can be carried without exceeding the weight capacity.

## sample

4 5
2 3
3 4
4 5
5 6

7

</p>