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