교통 신호등

키우트 시의 도로는 모두 격자로 놓여 있다. 남북으로 뻗은 도로는 애비뉴, 동서로 뻗은 도로는 드라이브라고 부른다.

애비뉴에는 서쪽부터 1번, 2번 순서로 번호가 붙어 있고, 드라이브에는 남쪽부터 1번, 2번 순서로 번호가 붙어 있다. 아래 그림이 그 배치를 보여 준다.

애비뉴와 드라이브가 만나는 모든 교차로에는 신호등이 있다. 초록불은 지나가도 좋다는 뜻이고, 빨간불은 그 자리에 멈추라는 뜻이다. 교차로에 도착했을 때 자기 방향이 빨간불이면 초록불로 바뀔 때까지 기다려야 한다. 도착하는 순간에 불이 빨간불로 바뀌는 경우도 마찬가지로 기다린다. 반대로 도착하는 순간에 초록불로 막 바뀌었다면 기다리지 않고 지나갈 수 있다.

한 교차로의 두 방향 신호는 항상 색이 다르다. 남북 방향이 초록불이면 동서 방향은 빨간불이고, 그 반대도 성립한다. 충돌을 막으려고 두 방향이 함께 초록불이 되는 일은 없고, 효율을 위해 함께 빨간불이 되는 일도 없다. 한쪽이 빨간불로 바뀌는 순간 다른 쪽이 초록불로 바뀐다. 각 신호등은 정해진 시간 간격을 영원히 반복한다.

지켜야 하는 신호는 교차로에 도착하는 순간 달리고 있던 방향의 신호다. 애비뉴를 따라 남북으로 달려서 도착했다면 남북 방향 신호를 보고, 드라이브를 따라 동서로 달려서 도착했다면 동서 방향 신호를 본다. 자기 방향이 초록불이면 직진하든 좌회전하든 우회전하든 기다리지 않고 교차로를 지난다.

내일 자동차로 친구 집에 간다. 되도록 빨리 도착하고 싶어서 시간이 가장 적게 걸리는 경로로 가려고 한다. 도로 지도와 모든 신호등의 설정이 주어질 때, 내 집에서 친구 집까지 걸리는 최소 시간을 구하는 프로그램을 작성하라.

자동차는 거리 1을 시간 1에 달린다. 좌회전, 우회전, 출발, 정지에 드는 시간은 0으로 본다. 다른 차는 생각하지 않는다. 출발 시각은 0이다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 형식은 다음과 같다.

w h
dA(1) dA(2) ... dA(w-1)
dD(1) dD(2) ... dD(h-1)
ns(1,1) ew(1,1) s(1,1)
...
ns(w,1) ew(w,1) s(w,1)
ns(1,2) ew(1,2) s(1,2)
...
ns(w,h) ew(w,h) s(w,h)
xs ys
xd yd

첫 줄의 두 정수 $w$와 $h$는 애비뉴의 수와 드라이브의 수다 ($2 \le w, h \le 100$). 다음 두 줄에는 각각 $w-1$개와 $h-1$개의 정수가 주어진다. $dA(i)$는 $i$번 애비뉴와 $i+1$번 애비뉴 사이의 거리이고, $dD(j)$는 $j$번 드라이브와 $j+1$번 드라이브 사이의 거리다 ($2 \le dA(i), dD(j) \le 1000$).

이어지는 $w \times h$개의 줄은 신호등 설정이다. 세 정수 $ns(i,j)$, $ew(i,j)$, $s(i,j)$는 $i$번 애비뉴와 $j$번 드라이브가 만나는 교차로의 신호등을 나타낸다. $ns(i,j)$는 남북 방향이 초록불인 시간, $ew(i,j)$는 동서 방향이 초록불인 시간이다 ($1 \le ns(i,j), ew(i,j) < 100$). $s(i,j)$는 시각 0에서의 상태다. 0이면 남북 방향이 초록불이고, 1이면 동서 방향이 초록불이다. 모든 신호등은 시각 0에 상태 $s(i,j)$로 막 바뀌었다.

마지막 두 줄은 내 집의 위치 $(xs, ys)$와 친구 집의 위치 $(xd, yd)$다. 좌표는 1번 애비뉴와 1번 드라이브가 만나는 교차로를 $(0, 0)$으로 잡은 값이다. x축은 드라이브와 나란하고, y축은 애비뉴와 나란하다. 동쪽으로 갈수록 x가 커지고, 북쪽으로 갈수록 y가 커진다. 두 집은 모두 이웃한 두 교차로 사이의 도로 위에 있고, 교차로와 겹치지 않는다.

모든 값은 정수이고 공백으로 구분된다.

0 두 개가 적힌 줄이 입력의 끝을 뜻한다. 이 줄은 테스트 케이스가 아니므로 처리하지 않는다. 테스트 케이스는 30개를 넘지 않는다.

각 테스트 케이스마다 내 집에서 친구 집까지 가는 데 걸리는 최소 시간을 한 줄에 출력한다.