存钱罐/piggy

题目描述

$时间限制: 1 Sec \\ 内存限制: 256 MB$

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

输入格式

输入的第 $1$行包含整数 $T$ ，表示测试用例的数量。

每个测试用例的第 $1$行都包含两个整数 $a,b$，分别表示空存钱罐和装满硬币的存钱罐的重量（以克计）。

第 $2$行包含一个整数 $n$，表示硬币的总数量。

接下来的 $n$ 行，每行都包含两个整数 $w,v$ 分别表示硬币的面值和重量。

数据范围：$1≤n≤500, 1≤w≤50000,1≤v≤10000, 1≤a≤b≤1000$

输出格式

对每个测试用例，都输出一行，包含 “The minimum amount of money in the piggy-bank is $x$.”，其中 $x$ 是存钱罐内的最小金额。

若无法确定，则输出 “This is impossible.”。

样例 #1

样例输入 #1

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

样例输出 #1

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.