5971: 进阶7.2.2 存钱罐
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：42
解决：20
题目描述
钱罐有个大问题，不打碎存钱罐就无法确定里面有多少钱。
所以可能互出现把存钱罐打碎后发现钱不够的情况。唯一的可能是，称一下存钱罐的重量，试着猜里面有多少钱。
已知存钱罐的重量和每种面值的硬币的重量，请确定存钱罐内的最小金额。
输入
第一行包含一个正整数T TT，表示测试用例的数量。
对于每个测试用例：
第一行都包含两个正整数e ee和f ( 1 ≤ e ≤ f ≤ 10000 ) f(1leq eleq fleq 10000)f(1≤e≤f≤10000)，分别表示存钱罐和装满硬币的存钱罐的重量(单位：克)。
第二行包含一个整数n ( 1 ≤ n ≤ 500 ) n(1leq nleq 500)n(1≤n≤500)，表示硬币的总数量。
接下来n nn行，每行都包含两个整数p pp和w ( 1 ≤ p ≤ 50000 , 1 ≤ w ≤ 10000 ) w(1leq pleq 50000, 1leq wleq10000)w(1≤p≤50000,1≤w≤10000)，分别表示硬币的面值和重量。
输出
对于每个测试用例，都输出一行，包含The Minimum amount is x.，其中x是存钱罐内的最小金额。
若无法确定，则输出Impossible...
样例输入 复制
3
10 110
2
1 1
30 50
10 110
2
1 1
30 30
1 6
2
10 3
20 4样例输出 复制
The Minimum amount is 60.
The Minimum amount is 100.
Impossible...