Twirling Robot

Time limit1sMemory limit128 MB

Summary

Find the cheapest sequence of override commands to steer a robot from the top-left cell to the bottom-right goal, where each cell forces a default move.

Level: Medium6 of 10
Topics: Shortest path, Graph, Dynamic programming, Greedy
Solved: No attempts yet

Problem

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.

Input

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$ .

Output

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.

Examples3

Example 1

Input

8 3
0 0 0 0 0 0 0 1
2 3 0 1 4 0 0 1
3 3 0 0 0 0 0 4
9 9 1 9
4 4
3 3 4 0
1 2 4 4
1 1 1 0
0 2 4 4
8 7 2 1
2 8
2 2
4 1
0 4
1 3
1 0
2 1
0 3
1 4
1 9 3 1
0 0

Expected output

1
11
6

Example 2
Input
```
2 2
0 1
4 4
1 1 1 1
0 0
```
Expected output
```
0
```
Example 3
Input
```
2 2
4 4
4 4
1 5 5 5
0 0
```
Expected output
```
6
```