밀물과 썰물 (큰 입력)

문제

지하 동굴 수로를 카약으로 지나던 중 밀물이 들어와 갇혔다. 다행히 동굴 지도는 가지고 있다. 썰물이 시작되기 전에는 밖으로 나갈 수 없으니 한동안 여기서 기다려야 한다. 그동안 물이 빠지기 시작한 뒤 출구까지 가장 빨리 가는 방법을 계산해 두려고 한다.

동굴은 $N$ 행 $M$ 열 격자다. 지도는 같은 크기의 격자 두 장으로 이루어지고, 한 장은 각 칸의 천장 높이를, 다른 한 장은 각 칸의 바닥 높이를 센티미터 단위로 적어 놓았다. 동굴 바닥은 물이 빠져나가는 재질이라 수위가 내려가면 수위보다 높은 곳에는 물이 남지 않는다.

출발 지점은 지도의 북서쪽 끝 칸이다. 현재 수위는 $H$ 센티미터이고, 물이 빠지기 시작하면 초당 10센티미터씩 일정하게 내려가 0이 된다. 출구는 남동쪽 끝 칸에 있다. 지금은 물에 잠겨 있지만 물이 빠지기 시작하는 순간부터 지나갈 수 있다.

어느 시점에서든 북, 남, 동, 서로 인접한 칸으로 이동한다. 이동은 다음 조건을 모두 만족해야 한다.

수위와 현재 칸의 바닥 높이와 이동할 칸의 바닥 높이가 모두 이동할 칸의 천장 높이보다 50센티미터 이상 낮아야 한다. 따라서 바닥과 천장 사이가 50센티미터 미만인 칸에는 어느 방향에서도 들어가지 못한다.
이동할 칸의 바닥 높이는 현재 칸의 천장 높이보다도 50센티미터 이상 낮아야 한다.
지도 밖으로는 나가지 못한다.

카약을 타고 높이는 얼마든지 오르내릴 수 있다. 예를 들어 위 조건만 만족하면 바닥 높이가 10센티미터인 칸에서 바닥 높이가 9000센티미터인 인접한 칸으로 갈 수 있다.

조건을 그림으로 나타내면 다음과 같다.

첫 번째 그림에서는 수위와 오른쪽 칸의 천장 높이 차이가 50센티미터에 못 미쳐서 오른쪽으로 가지 못한다.
두 번째 그림에서는 현재 칸의 바닥 높이와 오른쪽 칸의 천장 높이 차이가 50센티미터에 못 미쳐서 오른쪽으로 가지 못한다.
세 번째 그림에서는 오른쪽 칸의 바닥 높이와 그 칸 자신의 천장 높이 차이가 50센티미터에 못 미친다. 이 칸에는 어느 방향에서도 들어가지 못한다.
네 번째 그림에서는 오른쪽 칸의 바닥 높이와 현재 칸의 천장 높이 차이가 50센티미터에 못 미쳐서 오른쪽으로 가지 못한다.

한 칸에서 다른 칸으로 이동을 시작하는 순간에 떠나는 칸에 물이 20센티미터 이상 남아 있으면 카약을 탈 수 있어서 이동에 1초가 걸린다. 그렇지 않으면 카약을 끌어야 해서 10초가 걸린다. 걸리는 시간은 떠나는 칸의 물 높이로만 정해지고 도착하는 칸과는 무관하다.

썰물이 시작되기까지는 시간이 많이 남아서, 물이 빠지기 전에는 원하는 만큼 움직여도 된다. 중요한 것은 물이 빠지기 시작한 순간부터 출구에 닿을 때까지 걸리는 시간이다. 이 시간을 구하라.

입력

첫 줄에 테스트 케이스의 개수 $T$ 가 주어진다.

각 테스트 케이스의 첫 줄에는 세 정수 $H$ , $N$ , $M$ 이 주어진다. $H$ 는 처음 수위이고 단위는 센티미터이며, $N$ 과 $M$ 은 지도의 크기다. 그 뒤 $2N$ 개의 줄에 천장 높이와 바닥 높이가 다음 순서로 주어진다.

다음 $N$ 개의 줄에는 각각 $M$ 개의 정수가 공백으로 구분되어 주어진다. $i$ 번째 줄의 $j$ 번째 정수는 격자 위치 $(j, i)$ 의 천장 높이 $C_{ij}$ 이고 단위는 센티미터다. $i$ 가 커지는 방향이 남쪽, $j$ 가 커지는 방향이 동쪽이다.
그다음 $N$ 개의 줄에는 같은 형식으로 바닥 높이 $F_{ij}$ 가 주어진다.

출발 칸은 천장과 처음 수위 사이가 항상 50센티미터 이상이고, 천장과 바닥 사이도 항상 50센티미터 이상이다. 출구 칸은 천장과 바닥 사이가 항상 50센티미터 이상이다. 빠져나갈 길은 항상 존재한다.

제한

$1 \le T \le 50$
$1 \le N, M \le 100$
$1 \le H \le 10000$
$1 \le F_{ij} \le C_{ij} \le 10000$

출력

각 테스트 케이스마다 Case #x: t 형식으로 한 줄씩 출력한다. $x$ 는 1부터 시작하는 테스트 케이스 번호이고, $t$ 는 물이 빠지기 시작한 순간부터 동굴을 빠져나올 때까지 걸리는 시간이며 단위는 초다.

모든 사건은 0.1초의 정수배인 시각에만 일어나므로 답은 항상 0.1의 배수다. $t$ 는 소수점 아래 한 자리까지 출력하고, 값이 정수여도 소수점 아래 한 자리를 반드시 붙인다.

노트

물이 빠지기 전에 동굴을 모두 지나갈 수도 있다. 이때는 출구에서 물이 빠지기 시작하기를 기다리면 되므로 답은 0이다. 예제 입력의 네 번째 테스트 케이스가 이 경우다.

예제 입력의 첫 번째 테스트 케이스에서는 처음에 수위와 동쪽 칸 천장 사이가 33센티미터뿐이다. 그래서 물이 빠지기 시작한 뒤 1.7초를 기다려야 그 칸에 들어갈 수 있다. 들어갈 수 있게 된 시점에는 서쪽 칸의 물이 바닥에서 3센티미터 높이까지 내려가 있으므로, 출구까지 카약을 10초 동안 끌어야 한다.

두 번째 테스트 케이스는 상황이 낫다. 인접한 칸의 천장이 충분히 높아서 물이 빠지기 전에 $(1, 1)$ 까지 갈 수 있다. 거기서 수위가 90센티미터로 내려갈 때까지 1초를 기다린 다음 남쪽으로, 이어서 동쪽으로 카약을 저으면 빠져나온다. 모두 3초가 걸린다. $(2, 1)$ 은 천장이 높은데도 지나가지 못한다. 그 칸으로 들어갈 수 있는 칸인 $(1, 1)$ 과 $(2, 0)$ 의 천장과 그 칸 바닥 사이가 각각 10센티미터뿐이기 때문이다.

세 번째 테스트 케이스는 첫 번째와 비슷하다. 수위가 50센티미터로 내려갈 때까지 출발 칸에서 기다려야 한다. 그 뒤로는 출구를 향해 카약을 저을 수 있지만, 세 번 움직여 3초가 지나면 수위가 20센티미터, 즉 바닥보다 10센티미터 높은 상태가 되어 네 번째 이동은 카약을 끌게 된다.