0/1 Knapsack Problem

You are given a knapsack with a maximum weight capacity W and N items. Each item has a weight and a value. The task is to determine the maximum total value that can be obtained by selecting a subset of these items such that the total weight does not exceed W.

The problem follows the classic 0/1 knapsack formulation. The recurrence relation for dynamic programming is given by:

\(dp[i][w] = \max\left\{dp[i-1][w],\; dp[i-1][w-w_i] + v_i\right\}\) for \(w_i \leq w\), and \(dp[i][w] = dp[i-1][w]\) otherwise, where \(w_i\) and \(v_i\) are the weight and value of the \(i^{th}\) item.

Your solution should read input from standard input and write the result to standard output.

inputFormat

The input is provided via standard input and contains multiple lines:

1. The first line contains an integer W (the maximum weight the knapsack can hold).
2. The second line contains an integer N (the number of items).
3. The next N lines each contain two space-separated integers where the first integer is the weight \(w_i\) and the second integer is the value \(v_i\) of the item.

outputFormat

Output a single integer to standard output, which is the maximum value that can be achieved without exceeding the weight limit.

50
3
10 60
20 100
30 120

220