3619：Heroes of Might and Magic

After a very long journey and uncountable number of uphill battles, hero Raelag (who is the transformed Agrael, notice that "Raelag" is an anagram of "Agrael") finally find the map shows where the "Holy Cap" is. Now he is going to find the treasure.

The map is made up of squares of equal size which are arranged in r rows and c columns. At the beginning, Raelag is at the square Labeled 'S', and the "Holy Cap" is at the square Labeled 'T'. It is guarranteed that there is only one 'S' and only one 'T' in a map. Squares that labeled with '#' in the map means squares that can't be passed; '.' means roads that can be passed without any physical loss and squares that labeled with an integer i (1 ≤ i ≤ 9) means when Raelag pass through this square, he will suffer i points of physical loss. Squares that labeled with capital letter 'A', 'B', 'C', 'D' or 'E' means doors that can be passed only if Raelag has the right key (There are at most 5 kinds of doors in a map). The squares labeled with 'S', 'T' and other capital letters all can be passed with out physical loss. Raelag can move to squares only if that square share an edge with the square he is now in. Raelag can't move out of the map.

The fist line of input file contains a single integer T (1 ≤ T ≤ 10) - the number of test cases. For each test case, in the first line their are three integers: r, c and k (1 ≤ r, c ≤ 50, 0 ≤ k ≤ 5), representing the hight, length of the map and the number of kinds of doors in the map. Then there are r lines giving the map. Then k lines follows giving the position of the keys to the door 'A', 'B', 'C', 'D', and 'E' in order.

The uperleft conner is row 1 and colomn 1.

For each test case, output a single integer: the minimum points of physical lose Raelag needs to suffer to find the "Holy Cup". If he can't find the "Holy Cap" any way, output "-1".