Piggy-Bank

Before ACM can do anything, a budget must be prepared and the necessary financial support obtained. The main income for this comes from Irreversibly Bound Money (IBM). The idea is simple: whenever an ACM member has some small change, they take all the coins and drop them into a piggy-bank. This process is irreversible — the coins cannot be removed without breaking the pig. After enough time, the piggy-bank should hold enough cash to pay for everything that needs to be paid.

But piggy-banks have a big problem: there is no way to tell how much money is inside. So we might break the pig open only to find there is not enough money. We want to avoid this. The only option is to weigh the piggy-bank and estimate how many coins are inside. Assume we can measure the pig's weight exactly and that we know the weights of all coins of the given currency. Then there is a minimum amount of money we can guarantee is inside. Your task is to find this worst case: determine the minimum amount of cash inside the piggy-bank.

The input consists of T test cases. The number of test cases T is given on the first line.

Each test case begins with a line containing two integers E and F: the weight of an empty pig and the weight of the pig filled with coins, both in grams. No pig weighs more than 10 kg, so $1 \le E \le F \le 10000$.

The second line of each test case contains an integer N ($1 \le N \le 500$), the number of coin types used in this currency. The next N lines each describe one coin type with two integers P and W ($1 \le P \le 50000$, $1 \le W \le 10000$): P is the coin's value in monetary units and W is its weight in grams. Each coin type may be used any number of times.

For each test case, print exactly one line. If the given total weight can be made exactly with the coins, print The minimum amount of money in the piggy-bank is X. where X is the minimum total coin value that reaches that weight. If the weight cannot be reached exactly, print This is impossible..