Problem D
Rock Climbing

Peter is attempting to deep-water solo a rock climbing cliff over the ocean. Deep-water soloing (DWS) is a form of solo rock climbing that relies solely upon the presence of water at the base of the climb to protect against injury from falling.

Rock climbing is very exhausting and takes lots of energy. Since Peter is not very flexible, he can only move $1$ unit in any of the four directions: Up, Down, Left, and Right. Traveling to a different square will decrease Peter’s energy by the amount on that square. Note that the amount of energy on a square can be negative. In this case, Peter will gain energy.

If Peter’s energy is negative, he will fall into the water.

Peter doesn’t want to get wet, so he asks you to compute the minimum amount of energy he needs to complete the climb, assuming he takes an optimal route.

Input

The first line of the input will contain two integers, $R$, $C$ ($1\le R,C\le 15$). The second line of input will consist of a row of $C$ E characters, separated by spaces, representing the top of the cliff. These take $0$ units of energy to enter. Peter can choose any of them.

Next, there will be $R$ rows of $C$ columns of numbers $X_{r,c}$, where ($-9\le X_{r,c}\le 9$), the energy required to enter that section of cliff. The final line of input will consist of a row of $C$ S characters, representing the possible start points of the climb. These take $0$ units of energy to enter. Peter may return to any field, including the starting position, as often as he likes.

Output

Output a single integer, the minimum initial amount of energy necessary to complete the climb without falling.

5 5
E E E E E
1 2 3 4 5
5 4 3 2 1
-2 -2 -2 -2 -2
8 8 8 8 8
9 9 9 9 9
S S S S S

17

13 5
E E E E E
1 1 1 1 1
1 1 1 2 1
9 9 9 9 1
1 1 1 9 1
1 9 1 1 1
1 9 9 9 9
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
9 6 7 8 9
-5 9 -7 9 -5
6 0 7 0 5
S S S S S

32