求原题/题解

在ACM能够做任何事情之前，必须编制预算并获得必要的财政支持。这一行动的主要收入来自不可挽回的绑定资金(IBM)。背后的想法很简单。每当某位ACM成员有零钱时，他就会把所有的硬币都扔进储蓄罐里。你知道，这个过程是不可逆转的，硬币不能被移除而不打破猪。在足够长的时间后，储蓄罐里应该有足够的现金来支付所有需要支付的钱。

但存钱罐有一个大问题。要确定里面有多少钱是不可能的。因此，我们可能会把这头猪撕成碎片，结果却发现没有足够的钱。显然，我们希望避免这种令人不快的局面。唯一可能的办法是称一下储蓄罐，猜猜里面有多少硬币。假设我们能够准确地确定猪的重量，并且我们知道给定货币的所有硬币的重量。然后，我们可以保证在储蓄罐里有一些最低数额的钱。你的任务是找出这个最坏的情况，并确定储蓄罐内的最低现金数额。我们需要你帮助。不要再过早地折断猪了！

输入由T测试用例组成。在输入文件的第一行上给出它们的数目T（1<=T<=11）。每个测试用例都从包含两个整数E和F的一行开始，它们表示空猪和装满硬币的猪的重量。两种重量都以克为单位。任何猪的体重都不会超过10公斤，这意味着1<=E<=F<=10000。在每个测试用例的第二行中，有一个整数N(1<=N<=500)，它给出了在给定货币中使用的各种硬币的数量。下面是N行，每一行指定一种硬币类型。这些行分别包含两个整数，P和W(1<=P<=50000，1<=W<=10000)。P是以货币单位计算的硬币价值，W是以克为单位的重量。

为每个测试用例准确地打印一行输出。这一行必须包含“储蓄罐中的最低金额是X”这句话。其中X是使用给定总重量的硬币可以达到的最小金额。如果无法准确达到重量，请打印一行“这是不可能的”。

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.