favorite We need a little bit of your help to keep things running, click on this banner to learn more


Curious student Peter loves to program. Once he is so carried away by this thing that just fell asleep at the computer! Pete dreamed that he was in an alternate reality. Alternate Reality is a rectangular maze, which can be represented in a table sizeR×Ccells. In order not to miss school, Pete must find a way out of the labyrinth. Start position Petit denoted 'S', beginning from an alternate reality – 'E'. In one move, Peter moves into one of four adjacent cells (left, right, up, down). If the cell is occupied by the wall (the symbol 'X'), then Peter go into it can not. In some cells, there are doors with locks one of four colors ('R', 'G', 'B', 'Y'). For the passage in this box, you must have the key of color. Since multiple keys, one key can open any number of its corresponding locks.

The Lord of the alternative reality invites Pete to buy the keys to get to the exit. Our hero's very little money with him, so he wants to spend as little money and still get to the exit. Help him determine the minimum amount of money you'd spend on the keys.


The first line of the input file contains a number of tests. Each test starts with two integersR and C (1 <=R, C <= 50). The second line of the test consists of4integersPi, the cost of purchasing key 'R', 'G', 'B' and 'Y' respectively (Pi <= 100). Followed byRrows, each containingCcharacters, describing the maze. Each maze has only one symbol 'S' and one character 'E'.


For each test on a separate line, print out a minimum amount of money needed to purchase a set of keys, allowing to pass to the exit. If the path to the exit from an alternate reality does not exist, and Petya doomed to oversleep lessons, display "Sleep".

Time limit 1 second
Memory limit 64 MiB
Input example #1
3 7
1 1 1 1
6 6
1 5 3 1
Output example #1