已知一个空储钱罐的重量和装满硬币时的重量,给出储钱罐中有可能出现的硬币种类,每种硬币都有自身的重量和价值,问一个装满硬币的储钱罐的最少价值是多少?
输入第一行为一个整数T(1≤T≤10),表示有T组数据。
每组数据第一行有两个整数E和F(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.
时间限制 | 1 秒 |
内存限制 | 128 MB |