Show Me the Money

Frank Marks works at the business office of a large company whose customers use many different currencies. Employees come to the office with requisitions for specific amounts of money, such as 100 American dollars or 452 Euros. If Frank has enough of the requested currency on hand he gives exactly that amount; if he does not, he substitutes another currency instead.

When Frank has completely run out of the requested currency, he must pick a substitute. He may choose any currency whose value he can relate to the requested one through the known exchange rates, and he must provide at least the requested value (he may not go under). Among all such substitutes he wants the one whose value is as close as possible to the requisition without going under.

For example, suppose Frank knows the following exchange rates among six currencies A, B, C, D, E and F:

23 A = 17 B
16 C = 29 E
5 B = 14 E
1 D = 7 F

A rate v1 name1 = v2 name2 means that v1 units of name1 have exactly the same value as v2 units of name2. Suppose a requisition for 100 A arrives but Frank has no A. He could hand over 74 B (worth about 100.12 A), 115 C (worth about 100.72 A) or 207 E (worth about 100.02 A); the closest without going under is 207 E. Note that the given rates provide no way to relate A to D or to F, so those currencies cannot be used to satisfy a request stated in A.

Frank also stocks at most 100,000 units of any single currency, so a substitute currency can be used only if at most 100,000 of its units are needed. For instance, a requisition for 64,000 A cannot be met with E (it would need more than 100,000 units) and must instead be met with 73,078 C.

Given the exchange rates and a requisition, determine the ideal substitute currency and the number of its units, assuming Frank has none of the requested currency but is fully stocked on every other currency.

The input contains several test cases. Each test case begins with a line holding a positive integer n, the number of exchange rates. Each of the next n lines has the form

val1 name1 = val2 name2

where name1 and name2 are the names of two distinct currencies and val1 and val2 are positive integers at most 30 giving the ratio between them (val1 units of name1 have the same value as val2 units of name2). There are at most 8 distinct currency names, and each pair of currencies is listed at most once. A currency name consists of at most ten alphabetic characters. The rates are always consistent (there are no contradictions such as 1 A = 2 B, 1 B = 2 C and 1 C = 2 A holding together).

After the n rate lines comes a single line of the form

val name

giving the requested amount (a positive integer at most 100,000) and the name of the requested currency.

A line containing a single 0 follows the last test case.

For each test case, print a line of the form Case X: units name, where X is the test-case number (starting at 1) and units name is the substitute currency together with the number of its units — the value closest to the requisition that does not go under, assuming Frank has none of the requested currency but is fully stocked on every other currency. Each test case has a unique answer.