밀물이 들어오고, 썰물이 나간다

여러 지하 동굴로 이루어진 동굴계에서 카약을 타던 중, 갑자기 밀물이 들어오고 있어 갇혔다는 사실을 깨달았다! 다행히 동굴계의 지도가 있다. 썰물이 시작될 때까지는 갇혀 있어야 하므로, 한동안 이곳에 머물러야 한다. 그동안 썰물이 시작된 뒤 출구로 가는 가장 빠른 방법을 알아내려고 한다.

동굴계는 N×M 격자이다. 지도는 수로 이루어진 두 개의 N×M 격자로 구성된다. 하나는 각 격자 칸의 천장 높이를 나타내고, 다른 하나는 각 격자 칸의 바닥 높이를 나타낸다. 동굴계의 바닥은 물이 스며들 수 있으므로, 수위가 낮아지면 현재 수위보다 높은 곳에는 물이 남아 있지 않는다.

당신은 지도의 북서쪽 모서리에 갇혀 있다. 현재 수위는 H센티미터이며, 수위가 내려가기 시작하면 초당 10센티미터의 일정한 속도로 0까지 낮아진다. 출구는 지도의 남동쪽 모서리에 있다. 현재는 물에 잠겨 있지만, 수위가 내려가기 시작하는 즉시 통과할 수 있게 된다.

언제든지 다음 제약 조건을 만족하면서 북쪽, 남쪽, 동쪽 또는 서쪽의 인접한 칸으로 이동할 수 있다.

• 수위, 현재 칸의 바닥 높이, 인접한 칸의 바닥 높이는 모두 인접한 칸의 천장 높이보다 적어도 50센티미터 낮아야 한다. 참고: 이는 바닥과 천장 사이의 거리가 50센티미터 미만인 칸에는 절대로 들어갈 수 없다는 뜻이다.

• 인접한 칸의 바닥 높이는 현재 칸의 천장 높이보다도 적어도 50센티미터 낮아야 한다.

• 지도의 경계 밖으로는 절대로 이동할 수 없다. 카약을 타고 원하는 만큼 위나 아래로 이동할 수 있다는 점에 유의하라. (카약을 많이 타서 운동 능력이 매우 뛰어나다!) 예를 들어, 위의 제약 조건을 만족한다면 바닥 높이가 10센티미터인 칸에서 바닥 높이가 9000센티미터인 인접한 칸으로 이동할 수 있다.

이 제약 조건들은 아래에 그림으로 나타나 있다.

• 첫 번째 그림에서는 수위가 인접한 칸의 천장 높이보다 50센티미터 이상 낮지 않으므로 오른쪽으로 이동할 수 없다.

• 두 번째 그림에서는 현재 칸의 바닥 높이가 인접한 칸의 천장 높이보다 50센티미터 이상 낮지 않으므로 오른쪽으로 이동할 수 없다.

• 세 번째 그림에서는 인접한 칸의 바닥 높이가 그 칸의 천장 높이보다 50센티미터 이상 낮지 않으므로 오른쪽으로 이동할 수 없다. 어느 방향에서도 그 칸으로 들어갈 수 없다.

• 네 번째 그림에서는 인접한 칸의 바닥 높이가 현재 칸의 천장 높이보다 50센티미터 이상 낮지 않으므로 오른쪽으로 이동할 수 없다.

한 칸에서 다른 칸으로 이동할 때, 현재 칸에서 이동을 시작하는 순간 그 칸에 남아 있는 물의 깊이가 적어도 20센티미터라면 이동을 완료하는 데 1초가 걸린다(카약을 탈 수 있다). 그렇지 않으면 10초가 걸린다(카약을 끌고 가야 한다). 소요 시간은 들어가는 칸이 아니라 떠나는 칸의 수위에만 좌우된다는 점에 유의하라.

썰물이 시작되기까지는 한동안 시간이 있으므로, 수위가 내려가기 전에 원하는 만큼 오랫동안 이동할 수 있다. 중요한 것은 수위가 내려가기 시작한 순간부터 출구에 도착하는 순간까지 얼마나 많은 시간이 필요한가이다. 이 시간을 계산할 수 있는가?

제한

메모리 제한: 1GB. 테스트 세트당 시간 제한: 40초.

테스트 세트 1 (Visible Verdict)

1 ≤ T ≤ 50. 1 ≤ N, M ≤ 10. 1 ≤ H ≤ 1000. 1 ≤ $F_{xy}$ ≤ $C_{xy}$ ≤ 1000.

테스트 세트 2 (Hidden Verdict)

1 ≤ T ≤ 50. 1 ≤ N, M ≤ 100. 1 ≤ H ≤ 10000. 1 ≤ $F_{xy}$ ≤ $C_{xy}$ ≤ 10000.

• 첫 번째 줄에는 테스트 케이스의 수를 나타내는 하나의 정수 T가 주어진다.

• 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 처음에 정수 H, N, M이 들어 있는 한 줄로 시작하며, 이들은 각각 센티미터 단위의 초기 수위와 지도의 크기를 나타낸다. 이어지는 2N개의 줄에는 다음과 같이 천장과 바닥의 높이가 주어진다.

• 다음 N개의 줄에는 각각 공백으로 구분된 M개의 정수가 주어진다. i번째 행의 j번째 정수는 $C_{ij}$, 즉 격자 위치 (j, i)의 천장 높이를 센티미터 단위로 나타낸다. i 좌표가 증가하는 방향은 남쪽이고, j 좌표가 증가하는 방향은 동쪽이다.

• 다음 N개의 줄에는 같은 형식으로 바닥 높이를 나타내는 공백으로 구분된 M개의 정수가 주어진다.

• 시작 위치에서는 항상 천장과 초기 수위 사이에 적어도 50cm의 공기층이 있고, 천장과 바닥 사이의 거리는 적어도 50cm이다.

• 출구 위치에서는 천장과 바닥 사이의 거리가 항상 적어도 50cm이다.

• 빠져나갈 방법은 항상 존재한다(애초에 들어왔으므로!).

각 테스트 케이스마다 "Case #x: t"를 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 케이스 번호이고, t는 썰물이 시작된 순간부터 동굴계에서 빠져나올 때까지 걸리는 시간을 초 단위로 나타낸다. 정답과의 절대 오차 또는 상대 오차가 10^{-6} 이내인 답은 정답으로 인정된다.

썰물이 시작되기 전에 동굴계 전체를 통과할 수 있을 수도 있다. 이 경우 출구에서 썰물이 시작될 때까지 기다릴 수 있으므로 답은 영이어야 한다(예제 테스트 케이스 중 네 번째가 이에 해당한다).

첫 번째 예제 테스트 케이스에서는 처음에 수위와 동쪽 칸의 천장 사이의 거리가 33센티미터밖에 되지 않으므로, 썰물이 시작된 뒤 그 칸에 들어가려면 1.7초 동안 기다려야 한다. 그 칸에 들어갈 수 있게 되면 이동을 시작할 수 있지만, 이제 서쪽 칸의 물이 너무 얕아서(바닥보다 겨우 3센티미터 높다) 출구 지점에 도달하려면 다음 10초 동안 카약을 끌고 가야 한다.

두 번째 경우의 초기 상황은 더 낫다. 인접한 칸들에 머리 위 공간이 많이 있으므로, 예를 들어 썰물이 시작되기 전에 (1, 1)로 이동할 수 있다. 그곳에 도착하면 썰물이 시작되고 수위가 90cm까지 내려갈 때까지 기다려야 한다(한 초가 걸린다). 그러고 나서 카약을 타고 남쪽으로 이동한 뒤 동쪽으로 이동하여 빠져나올 수 있다(총 세 초가 걸린다). (2, 1)에 있는 동굴은 천장이 충분히 높더라도 통과할 수 없다는 점에 유의하라. 이 동굴의 바닥과 이곳으로 들어오기 위해 거칠 수 있는 어느 동굴의 천장 사이에도 공간이 너무 적기 때문이다. 그 동굴들은 (1, 1)와 (2, 0)이며, 각 경우의 공간은 10센티미터밖에 되지 않는다.

세 번째 경우는 첫 번째 경우와 어느 정도 비슷하다. 시작 위치에서 썰물이 내려가 수위가 50cm가 될 때까지 기다려야 한다. 그 뒤에는 출구를 향해 카약을 탈 수 있지만, 세 번 이동한 뒤(세 초가 걸린다) 수위는 20cm가 되고, 이는 바닥보다 겨우 10cm 높은 수위이므로 네 번째 이동에서는 카약을 타는 대신 끌고 가게 된다.

네 번째 경우에는 정말 운이 좋다! 썰물이 시작되기 전에도 즉시 출구로 가서 그곳에서 기다릴 수 있다.