开始 2024-05-05 00:00:00

20240505 完全背包(maoyu&li)

结束 2024-05-11 00:00:00
Contest is over.
当前 2024-12-22 09:02:08

A. 储钱罐

描述

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

输入

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

每组数据第一行有两个整数EF(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.

Submit

登录

注册
时间限制 1 秒
内存限制 128 MB
提交