Let's play a game using a robot on a rectangular board covered with a square mesh (Figure D-1). The robot is initially set at the start square in the northwest corner facing the east direction. The goal of this game is to lead the robot to the goal square in the southeast corner.

<image>

Figure D-1: Example of a board

The robot can execute the following five types of commands.

"Straight":
Keep the current direction of the robot, and move forward to the next square.
"Right":
Turn right with 90 degrees from the current direction, and move forward to the next square.
"Back":
Turn to the reverse direction, and move forward to the next square.
"Left":
Turn left with 90 degrees from the current direction, and move forward to the next square.
"Halt":
Stop at the current square to finish the game.

Each square has one of these commands assigned as shown in Figure D-2. The robot executes the command assigned to the square where it resides, unless the player gives another command to be executed instead. Each time the player gives an explicit command, the player has to pay the cost that depends on the command type.

<image>

Figure D-2: Example of commands assigned to squares

The robot can visit the same square several times during a game. The player loses the game when the robot goes out of the board or it executes a "Halt" command before arriving at the goal square.

Your task is to write a program that calculates the minimum cost to lead the robot from the start square to the goal one.

Input

The input is a sequence of datasets. The end of the input is indicated by a line containing two zeros separated by a space. Each dataset is formatted as follows.

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

The integers h and w are the numbers of rows and columns of the board, respectively. You may assume 2 ≤ h ≤ 30 and 2 ≤ w ≤ 30. Each of the following h lines consists of w numbers delimited by a space. The number s(i, j) represents the command assigned to the square in the i-th row and the j-th column as follows.

* 0: "Straight"
* 1: "Right"
* 2: "Back"
* 3: "Left"
* 4: "Halt"



You can assume that a "Halt" command is assigned to the goal square. Note that "Halt" commands may be assigned to other squares, too.

The last line of a dataset contains four integers c0, c1, c2, and c3, delimited by a space, indicating the costs that the player has to pay when the player gives "Straight", "Right", "Back", and "Left" commands respectively. The player cannot give "Halt" commands. You can assume that all the values of c0, c1, c2, and c3 are between 1 and 9, inclusive.

Output

For each dataset, print a line only having a decimal integer indicating the minimum cost required to lead the robot to the goal. No other characters should be on the output line.

Sample 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


Output for the Sample Input


1
11
6






Example

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


Output

1
11
6

import java.lang.reflect.Array;
import java.util.*;
import java.util.Map.Entry;


import static java.lang.Math.*;
import static java.lang.System.*;

class Main {
	public static Random rand=new Random();

	public int[] dx=new int[]{1,0,-1,0};
	public int[] dy=new int[]{0,1,0,-1};

	public void dfs(int y,int x,int d){
		//次の点に行く
		for(int i=0;i<4;i++){
			int _x=x+dx[i],_y=y+dy[i];
			if(!(0<=_x && _x <W && 0<=_y && _y<H))continue;
			int c=dp[y][x][d]+(map[y][x]==(i-d+4)%4?0:cost[(i-d+4)%4]);
			if(dp[_y][_x][i]>c){
				dp[_y][_x][i]=c;
				dfs(_y,_x,i);
			}
		}
	}

	class Task implements Comparable<Task>{
		int x,y,d;
		int cost;
		Task(int _x,int _y,int _d,int _cost){
			x=_x;y=_y;d=_d;cost=_cost;
		}

		@Override
		public boolean equals(Object o) {
			if(!(o instanceof Task))return false;
			Task t=(Task)o;
			return x==t.x && y==t.y && d==t.d;
		}

		@Override
		public int compareTo(Task o) {
			return cost-o.cost;
		}
	}

	int W,H;int[][] map;int[]  cost;
	int[][][] dp;
	public void run() {
		Case:while(true){
			W=sc.nextInt();H=sc.nextInt();
			if(W==0 && H==0)return;
			map=new int[H][W];
			for(int h=0;h<H;h++)for(int w=0;w<W;w++){
				map[h][w]=sc.nextInt();
			}

			cost=new int[4];
			for(int i=0;i<4;i++)
				cost[i]=sc.nextInt();

			dp=new int[H][W][4];//上下左右どこから来たか
			for(int h=0;h<H;h++)for(int w=0;w<W;w++){
				Arrays.fill(dp[h][w],100000000);
			}
			dp[0][0][0]=0;
			//dfs(0,0,0);

			//dijkstra
			boolean[][][] used=new boolean[H][W][4];
			PriorityQueue<Task> que=new PriorityQueue<Task>();
			que.add(new Task(0,0,0,0));
			while(!que.isEmpty()){
				Task t=que.poll();
				if(used[t.y][t.x][t.d])continue;

				//次の点に行く
				for(int i=0;i<4;i++){
					int _x=t.x+dx[i],_y=t.y+dy[i];
					if(!(0<=_x && _x <W && 0<=_y && _y<H))continue;
					int c=dp[t.y][t.x][t.d]+(map[t.y][t.x]==(i-t.d+4)%4?0:cost[(i-t.d+4)%4]);
					if(dp[_y][_x][i]>c){
						dp[_y][_x][i]=c;
						que.add(new Task(_x,_y,i,c));
					}
				}
				used[t.y][t.x][t.d]=true;
			}

			int m=Integer.MAX_VALUE;
			for(int i=0;i<4;i++)m=min(dp[H-1][W-1][i],m);
			ln(m);
		}
	}
	public static void main(String[] args) {
		new Main().run();
	}

	static Scanner sc=new Scanner(in);
	//output lib
	static final String br=System.getProperty("line.separator");
	static final String[] asep=new String[]{""," ",br,br+br};
	static String str(boolean o){
		return o?"YES":"NO";
	}
	static <K,V> String str(Map<K, V> map){
		StringBuilder sb=new StringBuilder();
		boolean isFirst=true;
		for(Entry<K,V> set:map.entrySet()){
			if(!isFirst)sb.append(br);
			sb.append(str(set.getKey())).append(":").append(str(set.getValue()));
			isFirst=false;
		}
		return sb.toString();
	}
	static <E> String str(Collection<E> list){
		StringBuilder sb=new StringBuilder();
		boolean isFirst=true;
		for(E e:list){
			if(!isFirst)sb.append(" ");
			sb.append(str(e));
			isFirst=false;
		}
		return sb.toString();
	}
	static String str(Object o){
		int depth=_getArrayDepth(o);
		if(depth>0)return _strArray(o,depth);
		return o.toString();
	}
	static int _getArrayDepth(Object o){
		if(!o.getClass().isArray() || Array.getLength(o)==0) return 0;
		return 	1+_getArrayDepth(Array.get(o,0));
	}
	//depth ex A[10]…1 A[10][10]…2 exception A[0]…0 A[10][0]…1 A[0][0]…0
	static String _strArray(Object o,int depth){
		if(depth==0) return str(o);
		StringBuilder sb=new StringBuilder();
		for(int i=0,len=Array.getLength(o);i<len;i++){
			if(i!=0)sb.append(asep[depth]);
			sb.append(_strArray(Array.get(o,i),depth-1));
		}
		return sb.toString();
	}
	static void pr(Object... os){
		boolean isFirst=true;
		for(Object o:os){
			if(!isFirst)out.print(" ");
			out.print(o);
			isFirst=false;
		}
	}
	static void ln(){
		out.println();
	}
	static void ln(Object... os){
		for(Object o:os){
			pr(o);ln();
		}
	}
}