SPOJ PIGBANK

Summary

Given the weight of a piggy bank and the weights and values of individual coins that could be contained in the piggy bank, calculate the minimum sum of the values of the coins.

Input

The first number T is the number of test cases to follow. Each test case begins with a line containing two integers $1\leq E\leq F\leq 10000$ representing the weight if the empty piggy bank and the weight of the full piggy bank respectively. The next line contains a single integer $1\leq N\leq 500$ representing the number of lines to follow. The following lines contain two integers $1\leq P\leq 50000,1\leq W\leq 10000$ representing the value and the weight of the coin types respectively.

Modest Proposal

Establish an array with dimension F-E+1 which will hold the minimum possible sum of money for a particular weight. Iterate over each coin value which has weight less than current index in array (i.e. the current weight) and check if the sum of money after including current coin value is less than the current sum of money. If yes, then replace with new sum. Answer is the sum of money for index F-E in array.

3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4

Output

The minimum amount of money in the piggy-bank is 60.
The minimum amount of money in the piggy-bank is 100.
This is impossible.