Warehouse Knapsack Optimization

You are given a warehouse that can store items up to a maximum weight W. There are n types of items available, where each item type i has a weight w_i and a value v_i. Your goal is to maximize the total value of items stored without exceeding the capacity W.

This is a typical 0/1 Knapsack problem. The state transition can be formulated in LaTeX as follows:

\( dp[j] = \max(dp[j],\ dp[j-w_i] + v_i) \) for \( j \ge w_i \).

You will be provided several test cases. Each test case starts with a line containing two integers W and n, followed by n lines each containing two integers \( w_i \) and \( v_i \). The input is terminated by a line "0 0" which should not be processed.

inputFormat

The input is read from standard input and consists of multiple test cases. Each test case is formatted as follows:

• The first line contains two integers: W (the maximum capacity of the warehouse) and n (the number of different item types).
• The next n lines each contain two integers: w_i (the weight of the item) and v_i (the value of the item).

The input terminates with a line containing "0 0" which should not be processed.

outputFormat

For each test case, output a single line containing the maximum total value achievable without exceeding the warehouse capacity W. The outputs for different test cases should be printed on separate lines to standard output.

## sample

50 3
10 60
20 100
30 120
100 2
50 200
50 300
0 0

220
500

</p>