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

Ромеро, охранник офисного здания в центре города Бингемтон, начал свой день, как любой другой. Однако, этот день был совсем другой, ибо Ромеро не знал, что всего за несколько часов до того, как он должен был проснуться, чтобы идти на работу, в новостях начали появляться сообщения о зомби.

Все больше и больше зомби бродили по улицам, ведущие ученые были озадачены, что не могут объяснить, почему это происходит. Примерно в полдень Ромеро пошел в кафетерий на обеденный перерыв. И только тогда, когда его обед был прерван криками, Ромеро заметил, что происходит что-то неладное. Едва он поднялся, чтобы посмотреть, кто там кричит, он увидел несколько зомби в кафетерии, которые приближались к нему. Напуганный, Ромеро быстро побежал в комнату службы безопасности и запер дверь.

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

Помогите Ромеро спасти своего друга и покинуть здание. Гаррисон не имеет оружия и доступа к камерам наблюдения и если Ромеро не спасет его, он останется в своем кабинете забаррикадированным и зомби в конечном счете нападут на него. Оба друга могут пройти через двери гораздо быстрее, чем зомби, а те, как вы знаете, довольно медленно двигаются и недостаточно умны, чтобы открыть дверь. Однако, зомби очень настырны, и будут ломиться в дверь, пока её не выломают. Чтобы спасти Гаррисона, Ромеро должен добраться до комнаты, где находится его друг раньше, чем зомби найдут его.

Благодаря камерам наблюдения Ромеро знает, где находиться его друг, а также какие комнаты заполнены зомби, а какие нет. Когда Ромеро заходит в комнату, где его ожидают зомби, он использует один патрон дробовика, для уничтожения зомби и продолжает свой путь. Если Ромеро заходит в комнату, где есть зомби и у него нет патронов, они одолеют его и убьют. Другими словами, при условии, что Ромеро начинает свой путь с К патронами, его путь из здания не должен пройти больше, чем через К комнат, наполненных зомби.

Входные данные

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

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

Выходные данные

Ваша программа должна вывести максимальное число друзей, оставшихся в живых. Если Ромеро не сможет убежать, ваша программа должна вывести "0", если Ромеро может спастись сам, но не может спасти Гаррисона, то программа должна вывести "1", если же Ромеро может спасти друга и успешно выбраться, то ваша программа должна вывести "2".

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