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".