0/1 Knapsack Problem

You are given n items, each with a positive integer weight and a positive integer value. You are also given a knapsack with a weight capacity W. The goal is to select a subset of these items such that the total weight is at most W and the total value is maximized. This problem can be formulated as:

Maximize \( \sum_{i=1}^{n} v_i x_i \) subject to \( \sum_{i=1}^{n} w_i x_i \leq W \) and \( x_i \in \{0, 1\} \), where \( w_i \) and \( v_i \) are the weight and value of the \( i\text{-th} \) item.

This is a classical dynamic programming problem.

inputFormat

Standard Input (stdin):

• The first line contains two integers: n (the number of items) and W (the weight capacity of the knapsack).
• The following n lines each contain two integers: the weight and the value of each item.

outputFormat

Standard Output (stdout): A single integer representing the maximum total value that can be achieved without exceeding the knapsack capacity.

4 10
5 10
4 40
6 30
3 50

90