던전 퀘스트 II

문제

"어둠의 덩어리"라고 불리는 동굴은 한때 악의 소굴이었지만, 용사가 마왕과 그 부하를 모두 쓰러뜨려 지금은 조용하다.

어느 날 용사는 마왕이 되살아날까 걱정이 되어, 경비 회사에 동굴 안 순찰을 의뢰했다.

동굴의 정보는 다음과 같다.

동굴은 $R$ 개의 행과 $C$ 개의 열로 이루어진 격자 모양의 평면이다.
어떤 칸에는 함정이 있고, 함정이 있는 칸에 들어간 사람은 체력을 잃는다.
함정의 종류는 여러 가지다. 체력을 크게 깎는 함정도 있고, 조금만 깎는 함정도 있다.

경비원이 순찰하는 방식은 다음과 같다.

경비원은 동굴의 왼쪽 위 칸에서 출발한다. 이 칸에는 함정이 없다.
경비원은 용사가 정해 준 경로를 그대로 따라 걷는다. 이 경로는 동굴 밖으로 나가지 않는다.
경비원은 체력을 회복할 물약을 챙겨 간다. 물약은 종류마다 한 병씩, 모두 $P$ 가지를 챙기므로 같은 물약을 두 번 마실 수는 없다.
물약은 다음 칸에 발을 들이기 바로 직전에만 마실 수 있다.
물약의 종류도 여러 가지다. 체력을 많이 회복하는 물약도 있고, 조금만 회복하는 물약도 있다. 체력은 최대 체력 $HP_{max}$ 까지만 회복되고, 넘치는 만큼은 사라진다.
한 번에 두 종류 이상의 물약을 마실 수 있다.
경비원의 체력이 0 이하가 되면 경비원은 죽는다.

경비원이 죽지 않고 순찰을 마칠 수 있는지 판정하는 프로그램을 작성하시오.

입력

입력은 여러 개의 데이터셋으로 이루어진다. 각 데이터셋의 형식은 다음과 같다.

HPinit HPmax
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
c(1) d(1)
...
c(T) d(T)
S
e(1) n(1)
...
e(S) n(S)
P
p(1)
...
p(P)

첫 줄에는 경비원의 초기 체력 $HP_{init}$ 과 최대 체력 $HP_{max}$ 가 주어진다. ( $0 < HP_{init} \le HP_{max} \le 1000$ )

다음 줄에는 $R$ 과 $C$ 가 주어진다. ( $1 \le R, C \le 100$ ) 이어서 $C$ 개의 문자로 이루어진 줄이 $R$ 개 주어져 동굴을 나타낸다. 문자 $a_{i,j}$ 는 $i$ 행 $j$ 열에 놓인 함정의 종류이고, 함정의 종류는 A부터 Z까지의 대문자로 적는다.

다음 줄에는 설명할 함정 종류의 수 $T$ 가 주어진다. 이어지는 $T$ 개의 줄에는 대문자 $c_i$ 와 정수 $d_i$ 가 주어지며, 함정의 종류와 그 함정이 깎는 체력을 뜻한다. ( $0 \le d_i \le 1000$ ) 동굴에 등장하는 함정의 종류는 모두 이 목록에 정확히 한 번씩 나온다.

다음 줄에는 용사가 정해 준 경로의 구간 수 $S$ 가 주어진다. ( $0 \le S \le 1000$ ) 이어지는 $S$ 개의 줄에는 문자 $e_i$ 와 정수 $n_i$ 가 주어지며, 경비원이 나아갈 방향과 그 방향으로 내딛는 걸음 수를 뜻한다. ( $\sum n_i \le 1000$ ) 방향은 위, 아래, 왼쪽, 오른쪽을 각각 뜻하는 U, D, L, R 중 하나다.

마지막으로 경비원이 챙긴 물약의 종류 수 $P$ 가 주어지고, 이어지는 $P$ 개의 줄에는 그 물약이 회복시키는 체력 $p_i$ 가 주어진다. ( $0 \le P \le 12$ , $0 < p_i \le 1000$ )

입력의 마지막 줄에는 0이 두 개 주어진다. 이 줄은 처리하지 않는다.

출력

각 데이터셋마다 경비원이 순찰을 무사히 마치면 YES를, 그러지 못하면 NO를 한 줄에 출력한다.

순찰이 끝난 시점에 경비원의 체력이 0 이하이면 NO를 출력한다.