Merchant's Maximum Value

A caravan merchant is on a journey and needs to maximize the total value of goods he can transport without exceeding his caravan's weight capacity. You are given an integer \(n\) representing the number of items, an integer \(W\) representing the maximum weight capacity, and \(n\) pairs of integers where each pair represents the weight and value of an item.

Your task is to determine the maximum total value that can be obtained by selecting items such that the sum of their weights does not exceed \(W\). This is a classic 0/1 knapsack problem. The recurrence relation for the dynamic programming solution is given by: $$dp[i][w] = \begin{cases} \max(dp[i-1][w],\;dp[i-1][w-w_i]+v_i) & \text{if } w_i \le w\\ dp[i-1][w] & \text{otherwise} \end{cases}$$ where \(w_i\) and \(v_i\) denote the weight and value of the \(i^{th}\) item respectively.

inputFormat

The input is given from stdin in the following format:

• The first line contains two integers \(n\) and \(W\), representing the number of items and the maximum weight capacity.
• Each of the next \(n\) lines contains two integers: the weight and the value of an item.

outputFormat

Output a single integer on stdout representing the maximum total value that can be achieved without exceeding the weight limit.

## sample

3 50
10 60
20 100
30 120

220

</p>