P1384. 小猪存钱罐

题目描述

在ACM开展任何活动前，必须准备预算并获取必要的资金支持。主要收入来源于"不可逆绑定资金"(IBM)。其原理很简单：每当ACM成员有零钱时，就把所有硬币投入存钱罐。这个过程是不可逆的——不打破存钱罐就无法取出硬币。经过足够长时间后，存钱罐里应该有足够的现金来支付所需费用。

但存钱罐存在一个大问题：无法确定里面有多少钱。我们可能打破存钱罐后才发现钱不够。显然需要避免这种尴尬情况。唯一的办法是称重并估算里面的硬币数量。假设我们能精确测量存钱罐重量，并且知道该货币所有硬币类型的重量。那么我们可以确保存钱罐内至少有多少钱。你的任务是找出这个最坏情况下存钱罐内的最小金额。我们需要你的帮助，让存钱罐不再被提前打破！

输入格式

输入包含$T$个测试用例。第一行给出测试用例数量$T$。每个测试用例包含：

• 第一行：两个整数$E$和$F$，表示空存钱罐和装满硬币后存钱罐的重量（克）。满足$1 \leq E \leq F \leq 10000$
• 第二行：整数$N$（$1 \leq N \leq 500$），表示货币的硬币种类数
• 接下来$N$行：每行两个整数$P$和$W$（$1 \leq P \leq 50000$，$1 \leq W \leq 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.

来源

Central Europe 1999