Knapsack on a Shelf

You are given a shelf that can hold a maximum weight W and N items, each with a specified weight and value. Your task is to determine the maximum total value that can be obtained by selecting a subset of these items such that the sum of their weights does not exceed W. This is a classic 0/1 knapsack problem.

The problem can be formulated as follows:

Given N items with weights \(w_i\) and values \(v_i\) for \(i = 1, 2, \dots, N\), and a shelf with capacity \(W\), choose a subset of items such that the total weight \(\sum_{i \in S} w_i \leq W\) and the total value \(\sum_{i \in S} v_i\) is maximized.

Note: If no subset of items can be chosen without exceeding the weight limit, the output should be 0.

inputFormat

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

N W
w1 v1
w2 v2
...
wN vN

Here, the first line contains two integers \(N\) (the number of items) and \(W\) (the maximum weight capacity of the shelf). Each of the following \(N\) lines contains two integers representing the weight and value of each item.

outputFormat

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

4 10
2 5
3 6
4 5
5 8

19