/*
ACMプログラミングコンテスト 過去問 2008年国内予選 Problem D

■ちょろちょろロボット

ロボットを使ったゲームをしよう．ロボットが 1 台，マス目状に区切られた長方形の盤面上に置かれている（図 D-1）．ロボットは，最初北西隅にあるスタート地点のマスに東方向を向いて配置されている．ゲームの目的は，ロボットを南東隅にあるゴールのマスまで誘導することである．

ロボットは，次の 5 種類の命令を実行することができる． 

「直進 (Straight)」: 
現在の進行方向のまま，次のマスに前進する． 
「右折 (Right)」: 
進行方向を 90 度右に変えて，次のマスに前進する． 
「反転 (Back)」: 
進行方向を 180 度変えて，次のマスに前進する． 
「左折 (Left)」: 
進行方向を 90 度左に変えて，次のマスに前進する． 
「停止 (Halt)」: 
現在のマスで止まって，ゲームを終了する． 

各マスには，上述の命令のいずれかが割り当てられている（例：図 D-2）．代わりに実行すべき別の命令をプレイヤーが与えない限り，ロボットは，現在いるマスの命令を実行する．プレイヤーが明示的に命令を与える際は，その都度，命令の種類に応じたコストを支払う必要がある．

ロボットは，同じ場所を何度も訪れることが許されている．一方で，ロボットが盤面外に前進するような命令を実行した場合や，ゴールに着く前に停止命令を実行した場合は，失格となる． 

あなたの仕事は，ロボットをスタート地点からゴール地点に誘導するために必要な最小コストを求めるプログラムを書くことである． 

Input
入力は，複数のデータセットからなり，入力の終わりはスペースで区切られたゼロ 2 つからなる行である．各データセットは，次の形式をしている． 


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 と w は，それぞれ盤面の行および列の数を示す整数であり， 2 <= h <= 30, 2 <= w <= 30 と仮定してよい．続く h 行はそれぞれ，スペースで区切られた w 個の文字から構成されており，文字 s(i, j) は， i 行 j 列目に位置するマスに割り当てられた命令を示す．その意味は，以下の通り． 

0: 「直進」命令 
1: 「右折」命令 
2: 「反転」命令 
3: 「左折」命令 
4: 「停止」命令 

ゴールのマス目には，「停止」命令が割り当てられているが，他のマス目にも「停止」命令が割り当てられていることがあるので，注意せよ． 

データセットの最後の行は，スペースで区切られた c0, c1, c2, c3 の 4 つの整数値を含んでおり，それぞれ，「直進」，「右折」，「反転」，「左折」命令を与える際に，プレイヤーが支払うべきコストを示している．プレイヤーが「停止」命令を与えることはできない．また， c0, c1, c2, c3 の値は， 1 以上 9 以下と仮定してよい． 

Output
各データセットについて，ロボットをゴールに誘導するために必要な最小コストを求め，十進数の整数としてそれぞれ 1 行に出力しなさい．出力行には他の文字があってはならない． 


■解答例

ロボットの状態を以下の情報で表す。
・位置 (x,y)
・ゴールかどうか
・向き
・ここまでにかかったコスト

向きは次のように、上向きの場合には0、右向きの場合は1と表す。

  0
3 R 1
  2

ロボットに与える指示には直進などがあり、それらは問題文により以下のように符号化されている。

0. 直進
1. 右折
2. 反転
3. 左折
4. 停止

4の停止はプログラムの終了を意味するため、使用することはない。それ以外の指示をロボットに提示した場合、ロボットの向きは現在の向きに指示の数字を加算して4で割ったあまりとなる。また、指示を実行した後の位置は、直進の場合には次のように変化する。

switch(direction){
case 0:
	y--;
	break;
case 1:
	x++;
	break;
case 2:
	y++;
	break;
case 3:
	x--;
	break;
}

ここでdirectionは、現在のロボットの向きである。例えばロボットに与える指示が右折(1)の場合、directionが0の場合にはx++、directionが1の場合にはy++となる。これは指示が直進(0)のときのdirectionに1を加えた時と同じである。そこで、directionと指示の数字を加算し、4で割ったあまりを求めると、その数字に対応したロボットの位置の変化は一意に決定できる。

switch((direction+cmd)%4){

よってswitch文の条件は上記のようになる。

このようにしてロボットの現在状態から指示を与えた場合の次のロボットの状態を求めることができる。そして、格子構造のグラフ探索アルゴリズムを適用すれば、本問題は解答を得ることができる。コストについては、盤面にあらかじめ記載されている指示はコスト0で実行でき、それ以外は指定されたコストで実行するとする。そしてすべての指示を適用した場合のロボットの次の状態を求め、探索に使用する。

探索アルゴリズムは、分岐限定法を使用する。4つの問題の解答を得るまでの時間は、Quad Coreプロセッサを用いて、4つの問題を並行して実行し約7分の時間を要した。

*/
import java.io.*;
import java.util.*;

public class Exp2008_D {
	/** ロボットの状態を表すクラス */
	static class Condition {
		/** オブジェクトが同じであるかどうかを調査する。 */
		public boolean equals(Object o){
			if(o instanceof Condition){
				Condition obj = (Condition)o;
				if(obj.x == this.x && obj.y == this.y && obj.goal == this.goal &&
					obj.direction == this.direction && obj.cost == this.cost){
					return true;
				}else{
					return false;
				}
			}else{
				return false;
			}
		}
		/** コンストラクタ */
		public Condition(int x,int y,boolean goal,int direction,int cost){
			this.x = x;
			this.y = y;
			this.goal = goal;
			this.direction = direction;
			this.cost = cost;
		}
		/** 文字列表現 */
		public String toString(){
			return new String("x,y="+x+","+y+" g:"+(goal?"1":"0")+" dir="+direction+" cost="+cost);
		}
		int x;
		int y;
		boolean goal;
		int direction;
		int cost;
	}
	/** 現在状態にコマンドを実行して次の状態を得る。 */
	private static Condition next(Condition now,int cmd,int cost){
		int x = now.x;
		int y = now.y;
		switch((now.direction+cmd)%4){
		case 0:
			y--;
			break;
		case 1:
			x++;
			break;
		case 2:
			y++;
			break;
		case 3:
			x--;
			break;
		}
		int direction = (now.direction+cmd)%4;
		return new Condition(x,y,false,direction,now.cost+cost);
	}
	/**　メイン関数 */
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new FileReader(args[0]));
		PrintWriter pw = new PrintWriter(new FileWriter(args[1]));

		while(true){
			String line = br.readLine();
			int col = Integer.parseInt(line.split(" ")[0]);
			int row = Integer.parseInt(line.split(" ")[1]);
			if(row == 0 && col == 0){
				break;
			}
			int[][] space = new int[row][col];
			for(int r=0;r<row;r++){
				line = br.readLine();
				String[] parts = line.split(" ");
				for(int c=0;c<col;c++){
					space[r][c] = Integer.parseInt(parts[c]);
				}
			}
			int[] costs = new int[4];
			line = br.readLine();
			String[] parts = line.split(" ");
			for(int cnt=0;cnt<costs.length;cnt++){
				costs[cnt] = Integer.parseInt(parts[cnt]);
			}

			Vector<Condition> open = new Vector<Condition>();
			open.add(new Condition(0,0,false,1,0));
			Vector<Condition> closed = new Vector<Condition>();

			while(open.size()!=0){
				Condition cnd = open.remove(0);
				if(cnd.goal == true){
//System.out.println(cnd.cost);
					pw.print(cnd.cost+"\n");
					break;
				}
				closed.add(cnd);
				for(int cmd=0;cmd<=3;cmd++){
					int cost = space[cnd.y][cnd.x]==cmd?0:costs[cmd];
					Condition next = next(cnd,cmd,cost);
					if(next.x == col-1 && next.y == row-1){
						next.goal = true;
					}
					if(!(next.x < 0 || next.y < 0 || next.x>=col || next.y>=row) && closed.contains(next)==false){
						// これから展開しようとしている状態と同じ状態であり、かつ、コストが大きい場合、その状態をopenから削除する。
						// また、コストが小さいものが既にopenにある場合、これから追加しようとしているノードは無視する（追加しない）。
						boolean notfind = true;
						for(int cnt=0;cnt<open.size();cnt++){
							Condition obj = open.get(cnt);
							if(obj.x == next.x && obj.y == next.y && obj.goal == next.goal &&
								obj.direction == next.direction){
								if(obj.cost > next.cost){
									open.remove(cnt);
									cnt--;
								}else{
									notfind = false;
								}
							}
						}
						if(notfind==true){
							open.add(next);
						}
					}
				}

				// コスト順にソートする
				Collections.sort(open,new Comparator<Condition>(){
					public int compare(Condition o1,Condition o2){
						if(o1.cost>o2.cost){
							return 1;
						}else if(o1.cost<o2.cost){
							return -1;
						}else{
							if(o1.goal==true && o2.goal==false){
								return -1;
							}else if(o1.goal==false && o2.goal==true){
								return 1;
							}else{
								return 0;
							}
						}
					}
				});
			}
		}

		br.close();
		pw.close();
	}
}