0/1 Knapsack

Problem statement

A field team packs indivisible instruments for a survey. Every instrument has a weight and a scientific value, and the team can carry only a fixed total weight. It wants the most valuable feasible subset. Your task Choose each item at most once to maximize total value without exceeding capacity W. Important details Items cannot be split or taken repeatedly. Leaving capacity unused is allowed. An item heavier than W cannot be selected. When using one-dimensional dynamic programming, process capacities in a direction that prevents reusing the same item. Worked example For items (weight 2, value 3), (3, 4), (4, 5) and W = 5, choose the first two items for value 7. Taking the last item alone gives only 5.

Input format

First line: n W. Next n lines: weight value.

Output format

Print the maximum total value.

Constraints

1 <= n <= 1000; 0 <= W <= 1000; 1 <= weights, values <= 1000.

Sample input

3 5
2 3
3 4
4 5

Sample output

7