0/1 Knapsack Problem

You are given a knapsack with a capacity \(W\) and \(n\) items, where each item \(i\) has a weight \(w_i\) and a value \(v_i\). Your task is to determine the maximum total value that can be carried in the knapsack without exceeding its capacity.

You cannot break an item, meaning each item can either be taken whole or left. Formally, you need to maximize the total value \(\sum_{i \in S} v_i\) subject to \(\sum_{i \in S} w_i \le W\), where \(S\) is a subset of the items.

Hint: Use dynamic programming with the recurrence:

[ \text{dp}[w] = \max(\text{dp}[w], \text{dp}[w - w_i] + v_i) \quad \text{for } w \ge w_i. ]

inputFormat

The input is given from stdin and has the following format:

• The first line contains two integers \(n\) and \(W\), where \(n\) is the number of items and \(W\) is the capacity of the knapsack.
• The next \(n\) lines each contain two integers representing the weight and value of an item.

outputFormat

Print a single integer to stdout representing the maximum total value that can be achieved under the given constraints.

4 10
5 10
4 40
6 30
3 50

90