Searching Treasure in Deep Sea
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.
1 5 10 0 0 ＃＃＃＃＃＃＃＃＃＃ ＃Ｓ ＃Ｋ ＃ Ｅ＃ ＃ ＃Ｋ ＃ ＃ ＃ Ｄ Ｄ ＃ ＃＃＃＃＃＃＃＃＃＃ 3 5 10 1 1 10 3 1 2 3 ＃＃＃＃＃＃＃＃＃＃ ＃ ＃ａＫＫＫＫ＃ ＃ＬＫＤｃＫＫＫＫ＃ ＃＃＃＃ｂＫＫＫＫ＃ ＃＃＃＃＃＃＃＃＃＃ ＃＃＃＃＃＃＃＃＃＃ ＃ ＤＬ Ｋ＃ ＃Ｈ ＃＃＃＃＃＃＃ ＃ Ｄ Ｄ Ｅ＃ ＃＃＃＃＃＃＃＃＃＃ ＃＃＃＃＃＃＃＃＃＃ ＃ ＃ ＃ Ｈ ＃ ＃ Ｓ ＃ ＃＃＃＃＃＃＃＃＃＃