Safety in Alchemy

Frederico de Vinci (one of Leonardo's less talented cousins) is a budding alchemist who spends his days mixing all sorts of chemicals, hoping to stumble upon the formula that turns lead into gold. Beside his worktable he keeps a cheap ceramic jar into which he tosses the useless and rather noxious results of his failed experiments.

The heat given off by the chemicals reacting in that jar has already caused a few accidents, cracking and even shattering his disposal jars.

Frederico has compiled a table of the temperature changes produced by various pairs of chemicals he has previously dropped into his disposal jars. (He believes that simultaneous interactions of three or more chemicals are insignificant.) For each pair, the table gives the temperature rise, in whole degrees, produced when 1 gram of the first chemical reacts with 1 gram of the second. Each such reaction consumes 1 gram of each chemical, and any given gram of a chemical can take part in at most one reaction.

Given this table and the list of chemicals (with quantities) that Frederico plans to drop into the jar, compute the maximum total temperature rise the contents may produce.

The input consists of one or more problem sets. The last problem set is followed by a line containing only the word ENDOFINPUT.

Each problem set begins with a list of up to 64 chemical pairs and the heat they produce. Each line has the form

chemical1 chemical2 heat

where chemical1 and chemical2 are chemical names, each an alphabetic string of 1 to 20 characters, and heat is an integer from 0 to 100 giving the number of degrees the jar's temperature rises when 1 gram of chemical1 reacts with 1 gram of chemical2. The order of the two names on a line does not matter, and no pair of chemicals appears more than once. This list is terminated by a line containing 0 0 0.

Next comes a list of up to 12 chemicals that Frederico plans to place in the jar. Each line has the form

chemical amount

where chemical is a chemical name (again an alphabetic string of 1 to 20 characters) and amount is an integer from 0 to 1000 giving the quantity in grams. No chemical appears more than once in this list. This list is terminated by a line containing 0 0.

For each problem set, print a single line of the form

The temperature in the jar will change by at most M degrees.

where M is the maximum total temperature rise, an integer.