Romero’s Dilemma#434
Romero, a security guard at an office building in downtown Binghamton, started his day as usual. However, this day was different. Just hours before he woke up to go to work, reports of zombies began appearing in the news.
As time went by, more zombies roamed the streets, and top scientists could not explain why this was happening. Around noon, Romero went down to the cafeteria for his lunch break. His lunch was interrupted by screams, and he realized something was wrong. When he stood up to see who was screaming, he saw several zombies in the cafeteria coming toward him. Terrified, Romero quickly ran to the security office and locked the door.
After overcoming the initial shock, Romero realized he could not remain locked in the office indefinitely. He checked the surveillance cameras and was horrified to see his coworkers being chased by zombies. The situation in the building was getting worse, and Romero understood that if he did not leave the building soon, zombies would fill the entire place. On the monitors, Romero saw that his friend Garrison had survived by barricading himself inside his office. Romero searched for weapons in the security office, but unfortunately, he found only a shotgun with a few shells left.
Help Romero rescue his friend and escape from the building. Garrison does not have a weapon or access to security cameras, and if Romero does not rescue him, Garrison will remain barricaded in his office and zombies will eventually attack him. Both friends can pass through doors faster than zombies, and zombies are slow and not smart enough to open doors. However, zombies are very persistent and will pound on doors until they break them down. To rescue Garrison, Romero must reach the room where Garrison is before the zombies do.
Thanks to the security cameras, Romero knows where his friend is, as well as which rooms are occupied by zombies and which are not. When Romero enters a room with zombies, he uses one shotgun shell to continue on his way. If he enters a room with zombies and has no shells left, they will overpower and kill him. In other words, if Romero starts his escape with shells, his path out of the building must pass through no more than rooms occupied by zombies.
The input consists of six blocks:
The first line gives the number of shotgun shells. The second line gives the name of the room where Romero is located, and the third line gives the name of the room where Garrison has barricaded himself. Then there is the number and a list of rooms that are initially occupied by zombies, each on a separate line. The fifth block is the number and a list of rooms with exit doors (each room name on a separate line). The input ends with the number and a list of internal doors (one per line). The description of an internal door consists of the names of the two rooms connected by the door, followed by two numbers: the time needed for Romero and Garrison to pass through the door, and the time required for zombies to break through and pass the door. You may assume that the second number is always greater than the first.
Your program should output the maximum number of friends that can survive. If Romero cannot escape, your program should output . If Romero can escape by himself but cannot rescue Garrison, your program should output . If Romero can rescue Garrison and successfully escape, your program should output .
You may assume that when Romero and Garrison are moving between rooms, they are not vulnerable to zombie attacks. You may also assume that if Romero and the zombies reach Garrison at the same time, Romero can protect his friend provided he has at least one shotgun shell left. Room names will not contain spaces, and there will be at most rooms and at most internal doors.
Example 1