Problem Description
A deep-sea salvage company found out that there was a sunken ship in some deep-sea area of the Pacific with a case of priceless treasure in it. The senior leaders concluded as followed:
There may be some sea monsters, they may cause some distraction. The company had some most advanced intelligent underwater robots. They were equipped with enough weapons to kill the monster.
After they research a map, they got information as follow (according to the Sample Input): S indicated the starting place. E indicated the place of the treasure case. D indicated the doors of the rooms in the ship. K indicated the keys which were needed while opening the doors. H indicated the stairs went up. L indicated the stairs went down. "#" indicated the walls which separated the rooms. Every lowercase in the map indicated a monster.
The enclosed space formed by the doors and the walls was called a separated room. Entering a room needed a key K to open a door D. After that, the key could not be used any more, the door would be open for ever, and there would be no need to use the key. The total number of rooms in the ship was not exceeding 30, the total number of the monsters in the ship was not exceeding 26, and the number of the monsters in each room would not exceed 3. There was no monster in the rooms where S and E, H and L were in.
The advanced intelligent underwater robot carried a machine gun whose cartridge clip capacity was 100 bullets and enough spare ammunition. It could re-load the bullets if given a chance. The surface of its body was equipped with 100 components. If all the components were destroyed while fighting with the monster, the robot could not function any more and would sink into the sea for ever. If only a part of the components was destroyed, the robot could recover if given a chance.The robot could attack the monsters in two ways; one is feign attack, and the other fierce attack. The feign attack would cause 1 reduction of the monsters' life value, and the fierce attack would cause a certain amount of deduction of the monsters' life value according to the degree of the fierce attack. The robot had 10 kinds of fierce attack tactics at most. Every attack tactics differed in bullet consumption and the certain reduction of the monsters' life value. For example, a certain kind of attack tactics would consume 30 bullets, and reduce 35 life value of the monster.
The life of the monster was so limited that when the injuries accumulated to a certain amount it would be killed. Suppose its life value was 100, and every attack would reduce a certain amount of life value.
When robot enters the treasure vessel, it searches the rooms one by one. As soon as it encounters the monsters, it will attack the monsters immediately. By consuming a certain amount of ammunition, a certain amount of the life value of the monsters is reduced. And then, the monsters attack the robot and destroy a certain number of robot's parts. Then they attack each other alternately like this. However, each time the robot launches attack firstly. If there are two or more monsters, the robot must kill the first one before another attack, and the monsters won't help each other in the battle. The choice of the order of attack is decisive when a number of monsters are in a room, because it closely relates with the final result of this battle.
The robot itself and machine guns it takes possess the capacity of restoration. The robot will re-load 2 bullets when it launches an attack. In the same room, the robot will repair 10 damaged parts of the body surface and re-filled cartridges after it kills a monster. The robot can't leave the room until all monsters are eradicated. At the time he leaves the room, 100 damaged parts are repaired and 100 cartridges are refilled again. It should be noted that, under no circumstances will the robot's parts and bullets of cartridges be more than 100.
Now intelligent underwater robot has been put into the sea, gradually approaching the location of the treasure vessel. Whether it can eradicate deep-sea monsters, and return the treasure box is the problem that you are supposed to resolve.
Input
There are several test cases. The first line of each case has 3 positive integers k, n and m (1 <= k <= 3, 1 <n, m <= 100), indicating that the deep-sea shipwreck is of k floors, each floor is a maze composed by n rows and m columns. (The Sample Input map is seen as below). That is, the maze is composed by characters of n lines, and each line has m characters. The following line has an integer p (0 <= p <= 10), indicating that there are p kinds of fierce attack tactics for the robot. Then there are a lines and each line has two positive integers, indicating the consumption of the number of bullets and reduction of the life value of the monsters as a result of injury by the robot's tactics. Then there is an integer q (0 <= q <= 26) taking up one line to indicate that there are q monsters in the treasure vessel. The following are q lines, and each line has one positive integer, indicating the number of damaged parts of the robot by those q monsters for one attack. Monsters are expressed in lowercase letters which are formed as a sequential increase from latter "a" to the letter "z". For example, when q = 10, then the names of the monsters are a, b, c, d, e, f, g, h, i, j, then the 10 lines of positive integers are the number of destroyed parts of robot as the result of the attack of those 10 monsters. Finally, there are k * n lines, every n lines indicates a floor of the ship, each line has m characters. The K floors are given from high to low. Input is terminated by the end of the file.
Output
For Each test case, if it can arrive "E" place, then output "Yes", or output "No". Each output takes up one line.
Sample Input
1 5 10
0
0
＃＃＃＃＃＃＃＃＃＃
＃Ｓ ＃Ｋ ＃ Ｅ＃
＃ ＃Ｋ ＃ ＃
＃ Ｄ Ｄ ＃
＃＃＃＃＃＃＃＃＃＃
3 5 10
1
1 10
3
1
2
3
＃＃＃＃＃＃＃＃＃＃
＃ ＃ａＫＫＫＫ＃
＃ＬＫＤｃＫＫＫＫ＃
＃＃＃＃ｂＫＫＫＫ＃
＃＃＃＃＃＃＃＃＃＃
＃＃＃＃＃＃＃＃＃＃
＃ ＤＬ Ｋ＃
＃Ｈ ＃＃＃＃＃＃＃
＃ Ｄ Ｄ Ｅ＃
＃＃＃＃＃＃＃＃＃＃
＃＃＃＃＃＃＃＃＃＃
＃ ＃
＃ Ｈ ＃
＃ Ｓ ＃
＃＃＃＃＃＃＃＃＃＃
Sample Output
No
Yes
