题目描述

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

输入

输入第一行为一个整数T(1≤T≤10)，表示有T组数据。

每组数据第一行有两个整数E和(1≤E≤F≤10000)，表示空储钱罐的重量和装满硬币时的重量。

第二行为一个整数N(1≤N≤500)，表示可能出现的硬币种类。

随后N行，每行两个整数，描述每一种硬币的价值P和重量W(1≤P≤50000,1≤W≤10000)。

输出

每组数据输出一行答案：

如果能计算出最少价值，输出The minimum amount of money in the piggy-bank is X.，其中X为最少价值；否则输出This is impossible.。

样例

输入复制

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

输出复制

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.