eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Дилема Ромеро

Дилема Ромеро

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Ромеро, охоронець офісної будівлі в центрі міста Бінгемтон, почав свій день, як і любий інший. Проте цей день був зовсім ішим, бо Ромеро ще не знав, що всього за декілька годин до того, як він повинен був проснутись, щоб йти на роботу, в новинах почали появлятись повідомлення про зомбі.

Все більше і більше зомбі бродили по вулицям, провідні вчені були здивовані і не могли пояснити, чому це відбувається. Приблизно опівдні Ромеро пішов до кафетерію на обідню перерву. І лише тоді, коли його обід було перервано криками, Ромеро помітив, що відбувається щось неладне. Як тільки він піднявся, щоб подивитись, хто там кричить, він побачив декілька зомбі в кафетерії, які наближались до нього. Наляканий, Ромеро швидко побіг в кімнату служби безпеки і закрив двері.

Подолавши перший шок, він зрозумів, що не може залишатись закритим в офісі на невизначений термін. Подивившись на зображення в камерах спостереження, він жахнувся, так як побачив своїх колег, керованих зомбі. Ситуація у будівлі все більше погіршувалась і він зрозумів, що якщо він не покине будівлю зараз, то зомбі заполонять все навколо. Також на моніторах Ромеро помітив, що вижив і його друг Гаррісон, забарикадувавшись у своєму кабінеті. Ромеро почав шукати в кімнаті охорони зброю, але, на жаль, він зміг знайти лише дробовик з декількоми патронами.

Допоможіть Ромеро спасти свого друга і покинути будівлю. Гаррісон не має зброї і доступу до камер спостережень і якщо Ромеро не спасе його, він залишиться забарикадованим у в своєму кабінеті і зомбі в кінці кінців нападуть на нього. Обидва друга можуть пройти через двері значно швидше, ніж зомбі, а ті, як ви знаєте, досить повільно рухаються і недостатньо розумні, щоб відкрити двері. Проте зомбі дуже настирні, і будуть ломитись у двері, доки їх не виломають. Щоб спасти Гаррісона, Ромеро повинен дістатись до кімнати, де знаходиться його друг раніше, ніж зомбі знайдуть його.

Завдяки камерам спостереження Ромеро знає, де знаходиться його друг, а також які кімнати заповнені зомбі, а які ні. Коли Ромеро заходить в кімнату, де його очікують зомбі, він використовує один патрон дробовика для знищення зомбі і продовжує свій шлях. Якщо Ромеро заходить в кімнату, де є зомбі і у нього немає патронів, вони здолають його і вб'ють. Іншими словами, при умові, що Ромеро починає свій шлях з К патронами, його шлях з будинку не повинен пройти більш, ніж через К кімнат, заповнених зомбі.

Вхідні дані

Вхідні дані складаються з наступних шести блоків даних:

У першому рядку задано кількість патронів у дробовику. У другому рядку задано назву кімнати, де знаходиться Ромеро, у третьому - назву кімнати, у якій забарикалувався Гаррісон. Далі йде кількість М і список кімнат, які вже заражені зомбі – кожна кімната у окремому рядку. П'ятим блоком задано кількість N і список кімнат, у яких є двері для виходу з будинку (назва кожної кімнати в окремому рядку). Завершує вхідні дані блок з кількістю J і списком внутрішніх дверей (також по одному опису в рядку). Описи внутрішніх дверей складаються з назв двох кімнат, між якими знаходяться двері, за якими йде два числа: час для Ромеро і Гаррісона, щоб пройти через двері, а друге натуральное число – час для зомбі, щоб зламати і пройти через ці двері. Можна припустити, що друге число завжди більше першого.

Вихідні дані

Ваша програма повинна вивести максимальну кількість друзів, що залишаться живі. Якщо Ромеро не зможе втікти, ваша програма повинна вивести "0", якщо Ромеро може спастись сам, але не може спасти Гаррісона, то програма повинна вивести "1", якщо ж Ромеро може спасти друга і успішно вибратись, то ваша програма повинна вивести "2".

Можна припустити, що в той час, коли Ромеро і Гарісон знаходяться на шляху між кімнатами, вони не є об'єктом для нападу зомбі. Можна також припустити, що якщо Ромеро і зомбі досягнуть Гаррісона одночасно, то Ромеро зможе захистити друга, при умові, що Ромеро має хоча б один патрон у дробовику. Назви кімнат не будуть містити пропусків, буде не більше 1000 кімнат, і не більше 5000 внутрішніх дверей.

Приклад

Вхідні дані #1
0
roomB
roomA
1
roomD
1
roomC
3
roomA roomB 1 15
roomB roomC 1 3
roomC roomD 1 3
Вихідні дані #1
1