Romero, a security guard at an office building in downtown Binghamton, started his day as any other. This day, however, would be very different. Unbeknownst to Romero, just hours before he woke up to go to work, reports had started appearing on the news about the dead walking. More and more zombies were roaming the streets, and the nation’s top scientists were baffled, unable to explain why this phenomenon was happening. Around noon, Romero went down to the cafeteria for his lunch break. It wasn’t until his break was interrupted by screams that Romero noticed something was wrong. As he stood up to see who was screaming, Romero saw several zombies in the cafeteria wandering towards him. Scared out of his wits, Romero quickly ran to the security office and locked the door. After getting over the initial shock and disbelief, Romero reasoned that he could not stay locked in the security office indefinitely. Romero watched the security cameras in horror as he saw his coworkers run from hoards of zombies. The situation in the building was getting worse and worse, and Romero realized that if he wanted to leave the building, he was going to have to leave very soon before the whole building was flooded with zombies. On the cameras, Romero noticed that his friend Garrison had survived by barricading himself inside his office. Romero searched the security office for weapons, but unfortunately he was only able to find a shotgun with a few shells remaining. Help Romero exit the building, rescuing Garrison if possible. Garrison does not have the benefit of a weapon or access to the security cameras, so unless Romero rescues Garrison, Garrison will remain barricaded in his office and zombies will eventually break through the barricade and attack him. Romero and Garrison will be able to pass through doors more quickly than the zombies. Zombies, as you may know from traditional zombie lore, are relatively slow moving, and are not smart enough to open doors. However, zombies are very persistent and will pound on doors until they break them down. In order to rescue Garrison, Romero’s path out of the building must simply pass through the room where Garrison is located before the zombies attack him. From his vantage point in the security office, Romero knows which rooms are initially infested with zombies and which rooms are initially safe. Over time, the zombies will break down doors and spread throughout the building. When Romero enters a room where there are zombies waiting for him, he will use one shotgun blast to evade the zombies and continue on his way. If Romero enters a room where there are zombies waiting for him and he has no more shotgun shells, the zombies will overpower Romero and kill him. In other words, given that Romero starts with \textit{k} shells, Romero’s path out of the building must not pass through more than \textit{k} rooms infested with zombies. \InputFile The input consists of six parts: 1) the number of shotgun shells Romero starts with; 2) the name of the room that Romero starts in; 3) the name of the room Garrison starts in; 4) the list of rooms that are initially infested with zombies; 5) the list of rooms containing exit doors; and 6) the list of internal doors. The first part is represented by an integer between 0 and 7 on a line by itself. The second part is represented by a string on a line by itself. The third part is also represented by a string on a line by itself. The fourth part is a list is represented by a nonnegative integer \textit{m} on a line by itself followed by \textit{m} room names, each on a line by itself. The fifth part is also a list represented by a nonnegative integer \textit{n} on a line by itself followed by \textit{n} room names, each on a line by itself. The sixth part is a list represented by a nonnegative integer \textit{j} on a line by itself followed by \textit{j} lines, each line describing an internal door. The description of an internal door consists of two strings followed by two positive integers. The two strings are the names of the two rooms that are connected by the door. The first positive integer is the amount of time it takes Romero and Garrison to pass through the door, and the second positive integer is the amount of time it takes zombies to pass through the door. You may assume that the second positive integer is always greater than the first positive integer. \OutputFile Your program should output the maximum possible number of survivors. If Romero cannot escape, your program should output "\textbf{0}". If Romero can escape but cannot save Garrison, your program should output "\textbf{1}". If Romero can save Garrison and successfully escape, your program should output "\textbf{2}". You may assume that while Romero and Garrison are in transit between rooms, they are not vulnerable to attack. You may also assume that if Romero and the zombies reach Garrison at the same time, Romero will be able to effectively protect Garrison, provided that Romero has at least one shotgun shell left. Room names will never contain whitespace (spaces, tabs, newlines), and there will be at most \textbf{1000} rooms and at most \textbf{5000} internal doors.