Fly By Night
By IX Maratona de Programação IME-USP, 2005 
Brazil
By IX Maratona de Programação IME-USP, 2005 Brazil
Bill Poucher announced in Shanghai (China), on last April, that the thirtieth ACM-ICPC World Final will be held in San Antonio (USA) on the second week of 2006.
Upon becoming aware of such information (a few months late), an air transport company on Texas - known as Fly by Night Ltd. - decided to take advantage of the event to increment its annual revenue.
The goal of the company's CEO was to offer air transport to the teams (including contestants and coaches) and to the support staff (those who make things work) from their cities of origin, in their countries of origin, to the contest site. Trying to ensure the success of his idea, the same CEO offered prices slightly below the market price for those who would be transported. As they were mostly students and professors, they accepted in a minute.
As you probably guessed, Fly by Night Ltd. operates night flights. However, instead of having its own airplanes, the company just sells seats in other companies' flights. The company gets a good comission due to the fact that those flights have, historically, a low occupation.
However, when the company's employees were checking the flights that were available for the operation, they had a big surprise. Most flights where completely full. Those who were not full didn't have many free seats. Nobody could explain the reason for the irregular demand. Two hypotheses were raised: the proximity of the american spring-break and the popularity of the contest. :-)
Trying to save the company (and his own position), the CEO realized it would be necessary to perform indirect flights and transfers. This way, the profit woud be lower, but nothing compared to the loss that the company would have by operating daytime flights or failing to transport the passengers (who, at the time, had already paid for their tickets).
The Fly by Night Ltd. employees proposed a set of scenarios with the flights that could be used. What was noticed shortly thereafter was that not all scenarios were viable, since they could not transport the necessary amount of passengers. Finally, the CEO noticed that he didn't have qualified staff to deal with the situation. You were hired to develop a program that, for each built scenario, answer if the scenario is viable or not.
A scenario, from now on, will be called instance. Your program must be prepared to deal with various instances.
Each instance starts with an integer 0 ≤ m ≤ 100 that specifies the number of origin cities of the passengers to be transported. A value m = 0 indicates the end of the instances and must not be processed. Otherwise, for each of the next m lines, the name of a city and the respective number of passengers from that city are given (an non-negative integer less than or equals to 100). The name of the city is between 1 and 20 caracters from the alphabet Σ={a,b,...,z,-}
In the next line are given an integer 0 ≤ n ≤ 100, that represents the number of flights in the instance, and the name of the city where the event will occur (the CEO decided that the program must accept that). The name of that city follow the same rules above.
In each of the n next lines are given the names of two cities of a flight (origin and destination, respectivelly), followed by a non-negative integer less than of equals to 200 that represents the number of free seats in that flight. Again, the names of the cities are from Σ and with length between 1 and 20. You can assume that there aren't two cities with the same name and that the cities of origin and destination are always different. Furthermore, Fly by Night Ltd. doesn't work with more than one flight between any two cities.
In each line of the input, any number of spaces may separate the provided data.
For each solved instance, you must print an identifier Instancia h, where h is an integer number, sequential and increasing from 1. On the next line, you must print viavel if it is possible to transport all passengers from their origin cities to the specified destination, and inviavel otherwise. A blank line must separate the output of each instance. Including the last instance.
| Sample Input | Sample Output |
|
3 |
Instancia 1 |