밀물과 썰물 (작은 입력)

동굴 수로를 카약으로 지나다가 밀물이 들어와 갇혔다. 다행히 동굴 지도는 있다. 물이 빠지기 시작할 때까지는 나갈 수 없으니, 그동안 출구까지 가장 빨리 가는 방법을 계산해 두려고 한다.

동굴은 $N \times M$ 격자이다. 지도는 $N \times M$ 크기의 숫자 격자 두 개로 이루어진다. 하나는 각 칸의 천장 높이이고, 다른 하나는 각 칸의 바닥 높이이다. 동굴 바닥은 물이 스며들기 때문에 수위가 내려가면 수위보다 높은 곳에는 물이 남지 않는다.

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

언제든지 인접한 칸으로 북, 남, 동, 서 방향 이동을 할 수 있다. 조건은 다음과 같다.

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

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

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

• 첫 번째 그림에서는 수위가 오른쪽 칸의 천장보다 50센티미터 이상 낮지 않아서 오른쪽으로 갈 수 없다.
• 두 번째 그림에서는 현재 칸의 바닥이 오른쪽 칸의 천장보다 50센티미터 이상 낮지 않아서 오른쪽으로 갈 수 없다.
• 세 번째 그림에서는 오른쪽 칸의 바닥이 그 칸 자신의 천장보다 50센티미터 이상 낮지 않아서 오른쪽으로 갈 수 없다. 이 칸에는 어느 방향에서도 들어갈 수 없다.
• 네 번째 그림에서는 오른쪽 칸의 바닥이 현재 칸의 천장보다 50센티미터 이상 낮지 않아서 오른쪽으로 갈 수 없다.

한 칸에서 다른 칸으로 이동을 시작하는 시점에 출발하는 칸에 물이 20센티미터 이상 남아 있으면 이동에 1초가 걸린다 (카약을 탈 수 있다). 그렇지 않으면 카약을 끌어야 해서 10초가 걸린다. 걸리는 시간은 출발하는 칸의 물 깊이로만 정해지고, 들어가는 칸의 물 깊이와는 상관없다.

물이 빠지기 시작할 때까지는 시간이 많이 남아 있어서, 그 전에는 원하는 만큼 이동해도 된다. 구해야 하는 값은 물이 빠지기 시작한 순간부터 출구에 도착할 때까지 걸리는 시간이다.

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

이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 초기 수위 $H$와 지도의 크기 $N$, $M$이 주어진다. 높이의 단위는 센티미터이다. 그 다음 $2N$개의 줄에 천장 높이와 바닥 높이가 다음 형식으로 주어진다.

• 다음 $N$개의 줄에는 각각 $M$개의 정수가 공백으로 구분되어 주어진다. $i$번째 줄의 $j$번째 정수는 $i$행 $j$열 칸의 천장 높이 $C_{ij}$이다. 행 번호는 남쪽으로 갈수록 커지고, 열 번호는 동쪽으로 갈수록 커진다.
• 그 다음 $N$개의 줄에는 같은 형식으로 바닥 높이 $F_{ij}$가 주어진다.

시작 칸은 천장과 초기 수위 사이가 항상 50센티미터 이상이고, 천장과 바닥 사이도 항상 50센티미터 이상이다.

출구 칸도 천장과 바닥 사이가 항상 50센티미터 이상이다.

빠져나가는 방법은 항상 존재한다.

제한

• $1 \le T \le 50$
• $1 \le N, M \le 10$
• $1 \le H \le 1000$
• $1 \le F_{ij} \le C_{ij} \le 1000$

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

$t$는 항상 0.1초의 배수이므로, 소수점 아래 첫째 자리까지 정확히 한 자리만 출력한다. 예를 들어 3초는 3.0으로, 11.7초는 11.7로 쓴다.

물이 빠지기 전에 동굴 전체를 지나갈 수도 있다. 이때는 출구에서 물이 빠지기를 기다리면 되므로 답이 0이다. 예제의 네 번째 케이스가 이 경우이다.

첫 번째 예제 케이스에서는 처음에 수위와 동쪽 칸 천장 사이가 33센티미터뿐이라서, 물이 빠지기 시작한 뒤 1.7초를 기다려야 그 칸에 들어갈 수 있다. 들어갈 수 있게 된 시점에는 서쪽 칸의 수위가 바닥보다 3센티미터밖에 높지 않아서, 출구까지 카약을 끌고 가는 데 10초가 걸린다.

두 번째 케이스는 시작 상황이 더 낫다. 인접한 칸의 천장이 충분히 높아서 물이 빠지기 전에 예를 들어 2행 2열 칸까지 갈 수 있다. 거기서 수위가 90센티미터로 내려갈 때까지 1초를 기다린 뒤 남쪽으로, 다시 동쪽으로 움직이면 3초 만에 빠져나온다. 2행 3열 칸은 천장이 높지만 그 칸의 바닥과 그리로 들어갈 수 있는 칸(2행 2열, 1행 3열)의 천장 사이가 각각 10센티미터뿐이라서 지나갈 수 없다.

세 번째 케이스는 첫 번째와 비슷하다. 수위가 50센티미터가 될 때까지 시작 칸에서 기다린 다음 출구 쪽으로 카약을 저어 간다. 세 번 움직여 3초가 지나면 수위가 20센티미터가 되는데, 바닥보다 10센티미터 높을 뿐이라서 네 번째 이동은 카약을 끌고 가야 한다.

네 번째 케이스에서는 물이 빠지기 전에 곧바로 출구까지 가서 기다릴 수 있다.