303002 - 储钱罐

已知一个空储钱罐的重量和装满硬币时的重量，给出储钱罐中有可能出现的硬币种类，每种硬币都有自身的重量和价值，问一个装满硬币的储钱罐的最少价值是多少？

Input

输入第一行为一个整数T(1≤T≤10)，表示有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.。

Examples

Input

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.
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题