Jungle Treasure Hunt

You are an archaeologist on a daring quest through a perilous jungle in search of a hidden treasure. The jungle is laid out as a grid with obstacles and traps. An empty cell is denoted by ., an impassable obstacle by #, and different types of traps by uppercase letters (e.g. A, B, C). Each trap reduces your stamina by a specified penalty.

If the archaeologist’s current stamina \(S\) is less than or equal to the penalty \(p\) of a trap, and if an energy drink is available, he will use the largest available energy drink to regain stamina before enduring the penalty. In other words, when hitting a trap the stamina is updated as follows:

[ S_{new} = \begin{cases} S + d - p, & \text{if } S \le p \text{ and an energy drink }d\text{ is available}\[6pt] S - p, & \text{otherwise} \end{cases} ]

The goal is to determine whether the archaeologist can start from the top-left cell and reach the bottom-right cell without his stamina dropping to zero or below at any moment.

inputFormat

The input consists of multiple test cases. For each test case:

• The first line contains two integers \(S_{init}\) and \(S_{max}\): the initial and maximum stamina.
• The second line contains two integers \(R\) and \(C\): the number of rows and columns in the grid.
• The next \(R\) lines each contain a string of length \(C\), representing the grid.
• The next line contains an integer \(T\), the number of trap types.
• Then follow \(T\) lines, each with a trap character and an integer penalty.
• The following line contains an integer \(P\), the number of energy drinks.
• Then \(P\) lines follow, each with an integer representing the stamina restored by that energy drink.

The input is terminated by a line containing "0 0" for \(S_{init}\) and \(S_{max}\).

outputFormat

For each test case, output a single line: YES if the archaeologist can reach the treasure, or NO otherwise.

## sample

15 20
4 4
.A..
....
..B.
..C.
3
A 5
B 8
C 12
3
10
15
5
10 10
5 5
.....
.#B#.
..A..
...#.
.....
2
B 5
A 3
2
10
10
5 10
2 2
.#
#.
0
0
0 0

YES
YES
NO

</p>