Dungeon Quest II#3306
The cave, called "Mass of Darkness", had been an agitating point of the evil, but the devil king and all of his soldiers were destroyed by the hero and the peace is there now.
One day, however, the hero was worrying about the rebirth of the devil king, so he decided to ask security agency to patrol inside the cave.
The information of the cave is as follows:
The cave is represented as a two-dimensional field which consists of rectangular grid of cells.
The cave has R \times C cells where is the number of rows and is the number of columns.
Some of the cells in the cave contains a trap, and those who enter the trapping cell will lose his hit points.
The type of traps varies widely: some of them reduce hit points seriously, and others give less damage.
The following is how the security agent patrols:
The agent will start his patrol from upper left corner of the cave.
There are no traps at the upper left corner of the cave.
The agent will patrol by tracing the steps which are specified by the hero.
The steps will be provided such that the agent never go outside of the cave during his patrol.
The agent will bring potions to regain his hit point during his patrol.
The agent can use potions just before entering the cell where he is going to step in.
The type of potions also varies widely: some of them recover hit points so much, and others are less effective.
Note that agent's hit point can be recovered up to HP_{max} which means his maximum hit point and is specified by the input data.
The agent can use more than one type of potion at once.
If the agent's hit point becomes less than or equal to , he will die.
Your task is to write a program to check whether the agent can finish his patrol without dying.
The input is a sequence of datasets. Each dataset is given in the following format:
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
The first line of a dataset contains two integers HP_{init} and HP_{max} (0 < HP_{init} \le HP_{max} \le 1000), meaning the agent's initial hit point and the agent's maximum hit point respectively.
The next line consists of and (1 \le R, C \le 100). Then, lines which made of characters representing the information of the cave follow. The character a_{i,j} means there are the trap of type a_{i,j} in -th row and -th column, and the type of trap is denoted as an uppercase alphabetic character [A-Z].
The next line contains an integer , which means how many type of traps to be described. The following lines contains a uppercase character [A-Z] and an integer d_i (0 \le d_i \le 1000), representing the type of trap and the amount of damage it gives.
The next line contains an integer (0 \le S \le 1000) representing the number of sequences which the hero specified as the agent's patrol route. Then, lines follows containing a character and an integer n_i (n_i \le 1000), meaning the direction where the agent advances and the number of step he takes toward that direction. The direction character will be one of 'U', 'D', 'L', 'R' for Up, Down, Left, Right respectively and indicates the direction of the step.
Finally, the line which contains an integer (0 \le P \le 12) meaning how many type of potions the agent has follows. The following lines consists of an integer p_i (0 < p_i \le 1000) which indicated the amount of hit point it recovers.
The input is terminated by a line with two zeros. This line should not be processed.
For each dataset, print in a line "YES" if the agent finish his patrol successfully, or "NO" otherwise. If the agent's hit point becomes less than or equal to at the end of his patrol, the output should be "NO".
Example 1