0/1 Knapsack Maximum Value

You are given a set of n items, each with a weight and a value. You also have a knapsack with a maximum weight capacity W. Your task is to determine the maximum total value of items that can be placed into the knapsack without exceeding its capacity. This is a classic 0/1 Knapsack Problem where each item can be used at most once.

The problem can be formulated as follows:

We have n items, where the i-th item has weight \(w_i\) and value \(v_i\). We want to maximize the sum \(\sum v_i\) such that the total weight \(\sum w_i\) does not exceed \(W\). Use dynamic programming to solve the problem by considering each item and updating the achievable values for weights from \(W\) down to \(w_i\).

inputFormat

The input is read from standard input (stdin) and has the following format:

n W
w1 v1
w2 v2
...
wn vn

Where:

• n is the number of items (an integer).
• W is the maximum weight capacity of the knapsack (an integer).
• Each of the next n lines contains two integers: the weight wi and the value vi of the i-th item.

outputFormat

The output should be printed to standard output (stdout) and consists of a single integer: the maximum total value achievable without exceeding the knapsack's capacity.

4 7
1 3
4 5
3 4
2 2

10