Twirling Robot

You control a robot on a rectangular board made of square cells. The robot starts on the cell in the northwest (top-left) corner, facing east. Your goal is to guide the robot to the goal cell in the southeast (bottom-right) corner.

The robot can carry out the following five commands:

• Straight: keep the current facing direction and move forward one cell.
• Right: turn 90 degrees clockwise from the current direction, then move forward one cell.
• Back: turn to the opposite direction, then move forward one cell.
• Left: turn 90 degrees counterclockwise from the current direction, then move forward one cell.
• Halt: stop on the current cell and finish the game.

Every cell has one of these commands assigned to it. On each step the robot performs the command assigned to the cell it currently occupies, unless you give it a different command to run instead. Every time you give an explicit command you must pay a cost that depends on the command type.

The robot may visit the same cell several times. You lose the game if the robot moves off the board, or if it performs a Halt command before reaching the goal cell.

Write a program that computes the minimum total cost needed to guide the robot from the start cell to the goal cell.

The input is a sequence of datasets. The end of the input is a line containing two zeros separated by a space. Each dataset has the following format.

w h
s(1,1) ... s(1,w)
s(2,1) ... s(2,w)
...
s(h,1) ... s(h,w)
c0 c1 c2 c3

$h$ and $w$ are the numbers of rows and columns of the board, with $2 \le h \le 30$ and $2 \le w \le 30$. Each of the next $h$ lines contains $w$ integers separated by spaces. The value $s(i, j)$ is the command assigned to the cell in row $i$, column $j$:

• 0: Straight
• 1: Right
• 2: Back
• 3: Left
• 4: Halt

The goal cell always has a Halt command; other cells may also have Halt. The last line gives four integers $c_0$, $c_1$, $c_2$, and $c_3$: the costs of giving the Straight, Right, Back, and Left commands, respectively. You cannot give a Halt command. Every cost satisfies $1 \le c_k \le 9$.

For each dataset, print a single line containing one integer: the minimum cost required to guide the robot to the goal. The line must contain nothing else.