Description

储蓄罐中有一定的金币,但数量未知.现要求在不破坏储蓄罐的前提下估计总价值.
已知储蓄罐当前的重量,空储蓄罐的重量,以及储蓄罐中的货币种类及对应的价值和重量.
你要做的任务就是根据给定的信息,估计储蓄罐中的最小价值量.

Input

第一行输入T,表明该问题有T组实例;
每组实例输入正整数E(空储蓄罐重量),F(当前储蓄罐重量);( 1 <= E <= F <= 10000 )
接着输入正整数N(货币种类数);( 1 <= N <= 500 )
接下来输入N行,每一行输入P,W,分别表示该种货币的价值和重量.( 1 <= P <= 50000, 1 <= W <= 10000 )

Output

如果该实例"可实现的"(根据给定的储蓄罐重量,经过计算不可能由该组实例的货币来实现的话,即确定该组实例为"不可实现的"),为每一个实例输出"The minimum amount of money in the piggy-bank is X.".其中"X"表示该实例的最小价值量.
如果该实例"不可实现的",则输出一行"This is impossible.".

Sample Input

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

Sample 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.

HINT

有多组测试数据

Source

软件协会、软件实训基地