140004 - Piggy-Bank

钱罐有个大问题,不打碎存钱罐,就无法确定里面有多少钱,所以可能会出现把存钱罐打碎后发现钱不够的情况。唯一的可能是,称一下存钱罐的重量,试着猜里面有多少钱。已知存钱罐的重量和每种面值的硬币重量,请确定存钱罐内的最小金额。

输入

输入的第1行包含整数T,表示测试用例的数量。
每个测试用例的第1行都包含两个整数e和f(1≤e≤f≤10000),分别表示空存钱罐和装满硬币的存钱罐的重量(以克计)。
第2行包含一个整数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.
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题