Transporting Supplies

You are given a set of datasets. For each dataset, you have a number of items and a maximum weight capacity. Each item has a weight and a value. Your task is to determine the maximum total value that can be carried without exceeding the weight capacity. This is a classic knapsack problem where you can either take an item or not.

Problem Details:

• Each dataset begins with two integers \(n\) and \(W\) separated by space, where \(n\) is the number of items and \(W\) is the weight capacity.
• The next \(n\) lines each contain two integers representing the weight and value of an item.
• The sequence of datasets is terminated by a line containing 0 0.

Your solution should output, for each dataset, a single integer on a new line which is the maximum value that can be achieved without exceeding the weight capacity.

Note: If no items are available (i.e. the input is 0 0 immediately), no output should be produced.

inputFormat

The input consists of multiple datasets. Each dataset starts with a line containing two integers \(n\) and \(W\) (\(1 \leq n \leq 1000\), \(W \geq 0\)). The following \(n\) lines each have two integers representing the weight and the value of an item. The input ends with a line containing 0 0.

Input is read from standard input (stdin).

outputFormat

For each dataset, output a single integer on its own line which indicates the maximum total value that can be obtained without exceeding the given weight capacity. Output the result to standard output (stdout).

4 5
2 3
1 2
3 4
2 2
0 0

7