회전하는 로봇

정사각형 칸들로 이루어진 직사각형 판 위에서 로봇을 조종한다. 로봇은 처음에 북서쪽(왼쪽 위) 모서리 칸에서 동쪽을 바라보며 놓여 있다. 목표는 로봇을 남동쪽(오른쪽 아래) 모서리의 도착 칸까지 이끄는 것이다.

로봇은 다음 다섯 가지 명령을 수행할 수 있다.

• 직진(Straight): 현재 방향을 그대로 유지하고 앞으로 한 칸 이동한다.
• 우회전(Right): 현재 방향에서 시계 방향으로 90도 회전한 뒤 앞으로 한 칸 이동한다.
• 후진(Back): 반대 방향으로 돌아선 뒤 앞으로 한 칸 이동한다.
• 좌회전(Left): 현재 방향에서 반시계 방향으로 90도 회전한 뒤 앞으로 한 칸 이동한다.
• 정지(Halt): 현재 칸에 멈춰 게임을 끝낸다.

각 칸에는 이 명령 중 하나가 배정되어 있다. 로봇은 매 단계마다 자신이 있는 칸에 배정된 명령을 수행하지만, 당신이 다른 명령을 내리면 그 명령을 대신 수행한다. 명령을 직접 내릴 때마다 명령 종류에 따른 비용을 지불해야 한다.

로봇은 같은 칸을 여러 번 방문할 수 있다. 로봇이 판 밖으로 나가거나, 도착 칸에 이르기 전에 정지 명령을 수행하면 게임에서 진다.

로봇을 시작 칸에서 도착 칸까지 이끄는 데 필요한 최소 총비용을 계산하는 프로그램을 작성하라.

입력은 여러 개의 데이터셋으로 이루어진다. 입력의 끝은 공백으로 구분된 두 개의 0으로 이루어진 줄로 표시된다. 각 데이터셋의 형식은 다음과 같다.

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 \le h \le 30$, $2 \le w \le 30$이다. 이어지는 $h$개의 줄에는 각각 공백으로 구분된 $w$개의 정수가 있다. 값 $s(i, j)$는 $i$번째 행, $j$번째 열의 칸에 배정된 명령을 나타낸다.

• 0: 직진(Straight)
• 1: 우회전(Right)
• 2: 후진(Back)
• 3: 좌회전(Left)
• 4: 정지(Halt)

도착 칸에는 항상 정지 명령이 배정되어 있으며, 다른 칸에도 정지가 배정될 수 있다. 마지막 줄에는 네 정수 $c_0$, $c_1$, $c_2$, $c_3$이 주어지는데, 이는 각각 직진, 우회전, 후진, 좌회전 명령을 내릴 때 지불하는 비용이다. 정지 명령은 직접 내릴 수 없다. 모든 비용은 $1 \le c_k \le 9$를 만족한다.

각 데이터셋에 대해, 로봇을 도착 칸까지 이끄는 데 필요한 최소 비용을 나타내는 정수 하나만을 한 줄에 출력한다. 그 줄에는 다른 문자가 있어서는 안 된다.