0/1 Knapsack Problem

You are given a set of n items, where each item i has a weight \(w_i\) and a value \(v_i\). You are also given a knapsack with a maximum weight capacity \(C\). The goal is to determine the maximum total value that can be obtained by selecting a subset of the items such that the sum of their weights does not exceed \(C\).

Your task is to solve this problem using dynamic programming. One approach is to use a DP table \(dp[i][w]\), which represents the maximum value achievable using the first \(i\) items with a knapsack capacity \(w\). The recurrence is given by:

\[ dp[i][w] = \begin{cases} dp[i-1][w], & \text{if } w_i > w,\\ \max(dp[i-1][w],\, dp[i-1][w-w_i] + v_i), & \text{if } w_i \leq w. \end{cases} \]

Output the maximum value that can be obtained without exceeding the knapsack capacity.

inputFormat

The input is given via standard input (stdin) and has the following format:

• The first line contains two integers \(n\) and \(C\) where \(n\) is the number of items and \(C\) is the capacity of the knapsack.
• The next \(n\) lines each contain two integers \(w_i\) and \(v_i\), representing the weight and value of the \(i\)-th item.

outputFormat

Output a single integer to the standard output (stdout) representing the maximum total value achievable without exceeding the capacity \(C\).

## sample

1 2
2 3

3