Gold Rush#1664
Petya, the alchemist, has invented the philosopher's stone, which allows him to perform alchemical reactions to transform substances into others. The mass of the substance being transformed and the mass of each resulting substance is exactly one gram. The law of conservation of mass may not apply, as Petya is unaware of it.
Initially, Petya has one gram of lead. Using the philosopher's stone, he can transform this lead into other substances, which can themselves be further transformed using the philosopher's stone. By performing a sequence of alchemical reactions, Petya aims to obtain as much gold as possible.
You are required to write a program to determine the maximum amount of gold Petya can produce, given the descriptions of the alchemical reactions possible with the philosopher's stone.
The first line of the input contains an integer — the number of different substances participating in and resulting from the alchemical reactions (1 \leq K \leq 6). The second line contains the names of these substances separated by spaces (the list must include lead ("svinec") and gold ("zoloto")). The names of substances are no longer than characters.
The third line contains an integer — the number of types of reactions that can be performed by the philosopher's stone (1 \leq L \leq 100). Then follow descriptions of these reactions. Each reaction description consists of two lines: the first line contains the name of the substance being transformed, and the second line lists the names of the substances produced as a result of the reaction.
Your program should output either a single integer equal to the required grams of gold, or the message "QUANTUM SATIS" (Latin for "As much as needed") if Petya can obtain any desired amount of gold.
Example 1