Dungeon Quest II
Печера, відома як "Маса Темряви", колись була осередком зла, але після того, як герой знищив короля дияволів і всіх його воїнів, там запанував мир.
Однак одного дня герой занепокоївся можливим відродженням короля дияволів, тому вирішив звернутися до охоронної агенції з проханням патрулювати печеру.
Інформація про печеру така:
Печера представлена у вигляді двовимірного поля, що складається з прямокутної сітки клітин.
Печера має R×C клітин, де R — кількість рядків, а C — кількість стовпців.
Деякі клітини печери містять пастки, і ті, хто потрапляє в пасткову клітину, втрачають очки життя.
Типи пасток різноманітні: деякі серйозно зменшують очки життя, а інші завдають меншої шкоди.
Ось як патрулює охоронець:
Агент починає патруль з верхнього лівого кута печери.
У верхньому лівому куті печери немає пасток.
Агент патрулює, слідуючи крокам, які вказав герой.
Кроки надані так, щоб агент ніколи не виходив за межі печери під час патрулювання.
Агент має з собою зілля для відновлення очок життя під час патрулювання.
Агент може використовувати зілля безпосередньо перед входом у клітину, куди він збирається ступити.
Типи зіль також різноманітні: деякі відновлюють багато очок життя, а інші менш ефективні.
Зверніть увагу, що очки життя агента можуть бути відновлені до HP_max, що є максимальними очками життя, вказаними у вхідних даних.
Агент може використовувати більше одного типу зілля одночасно.
Якщо очки життя агента стають меншими або рівними 0, він загине.
Ваше завдання — написати програму, щоб перевірити, чи може агент завершити свій патруль, не загинувши.
Вхідні дані
Вхідні дані складаються з кількох наборів даних. Кожен набір даних подається у наступному форматі:
HP_init HP_max R C a_{1,1} a_{1,2} ... a_{1,C} a_{2,1} a_{2,2} ... a_{2,C} ... a_{R,1} a_{R,2} ... a_{R,C} T [A-Z] d_1 [A-Z] d_2 ... [A-Z] d_T S [UDLR] n_1 [UDLR] n_2 ... [UDLR] n_S P p_1 p_2 ... p_P
Перший рядок набору даних містить два цілі числа HP_init і HP_max (0 < HP_init ≤ HP_max ≤ 1000), що означають початкові очки життя агента і максимальні очки життя агента відповідно.
Наступний рядок містить R і C (1 ≤ R, C ≤ 100). Далі йдуть R рядків, кожен з яких складається з C символів, що представляють інформацію про печеру. Символ a_{i,j} означає, що в i-му рядку і j-му стовпці є пастка типу a_{i,j}, а тип пастки позначається великою літерою [A-Z].
Наступний рядок містить ціле число T, що вказує кількість типів пасток, які будуть описані. Наступні T рядків містять велику літеру [A-Z] і ціле число d_i (0 ≤ d_i ≤ 1000), що представляють тип пастки і кількість шкоди, яку вона завдає.
Наступний рядок містить ціле число S (0 ≤ S ≤ 1000), що представляє кількість послідовностей, які герой вказав як маршрут патрулювання агента. Потім слідують S рядків, що містять символ і ціле число n_i (n_i ≤ 1000), що означають напрямок, у якому агент рухається, і кількість кроків, які він робить у цьому напрямку. Символ напрямку буде одним з 'U', 'D', 'L', 'R' для Вгору, Вниз, Ліворуч, Праворуч відповідно і вказує напрямок кроку.
Нарешті, рядок, що містить ціле число P (0 ≤ P ≤ 12), що означає, скільки типів зіль має агент. Наступні P рядків складаються з цілого числа p_i (0 < p_i ≤ 1000), яке вказує кількість очок життя, які воно відновлює.
Вхідні дані завершуються рядком з двома нулями. Цей рядок не слід обробляти.
Вихідні дані
Для кожного набору даних виведіть у рядку "YES", якщо агент успішно завершує свій патруль, або "NO" в іншому випадку. Якщо очки життя агента стають меншими або рівними 0 в кінці його патрулювання, вихід повинен бути "NO".