Tide Goes In, Tide Goes Out (Large)

You are kayaking through a system of underground caves when the tide comes in and traps you. You do have a map of the cave system. You cannot get out until the tide starts going out, so you will be here for a while. In the meantime you want to work out the fastest way to the exit once the water starts falling.

The cave system is an $N$ by $M$ grid. Your map is two grids of the same size: one gives the ceiling height of each square, the other gives the floor height of each square, both in centimeters. The floor of the cave system is porous, so as the water level falls, no water stays above the water level.

You are trapped at the north-west corner of the map. The current water level is $H$ centimeters, and once it starts going down it drops at a constant rate of 10 centimeters per second, down to zero. The exit is at the south-east corner of the map. It is covered by water now, and it becomes passable as soon as the water starts going down.

At any time you can move north, south, east or west to an adjacent square. A move must satisfy all of these constraints.

• The water level, the floor height of your current square, and the floor height of the adjacent square must all be at least 50 centimeters lower than the ceiling height of the adjacent square. This means you can never enter a square with less than 50 centimeters between its floor and its ceiling.
• The floor height of the adjacent square must also be at least 50 centimeters below the ceiling height of your current square.
• You can never move off the edge of the map.

You can go up or down as much as you want with your kayak. For example, you can go from a square whose floor is at height 10 centimeters to an adjacent square whose floor is at height 9000 centimeters, as long as the constraints above hold.

The constraints are illustrated below.

• In the first image you cannot move to the right because the water level is less than 50 centimeters below the ceiling height of the adjacent square.
• In the second image you cannot move to the right because the floor height of your current square is less than 50 centimeters below the ceiling height of the adjacent square.
• In the third image you cannot move to the right because the floor height of the adjacent square is less than 50 centimeters below the ceiling height of that same square. You can never enter that square from any direction.
• In the fourth image you cannot move to the right because the floor height of the adjacent square is less than 50 centimeters below the ceiling height of the current square.

When you move from one square to another, the move takes 1 second if at least 20 centimeters of water remain on the square you are leaving at the moment you start the move, because you can use your kayak. Otherwise you have to drag the kayak and the move takes 10 seconds. The time depends only on the water level in the square you leave, not in the square you enter.

It will be a while before the tide starts going out, so you can spend as much time moving as you want before the water starts going down. What matters is the time from the moment the water starts going down until the moment you reach the exit. Compute that time.

The first line contains a single integer $T$, the number of test cases.

Each test case starts with a line containing three integers $H$, $N$ and $M$: the initial water level in centimeters, and the map dimensions. The next $2N$ lines contain the ceiling and floor heights as follows.

• The next $N$ lines contain $M$ space separated integers each. The $j$-th integer in the $i$-th row is $C_{ij}$, the ceiling height in centimeters at grid location $(j, i)$, where increasing $i$ goes south and increasing $j$ goes east.
• The next $N$ lines contain the floor heights $F_{ij}$ in the same format.

At the starting location there are always at least 50 centimeters of air between the ceiling and the starting water level, and at least 50 centimeters between the ceiling and the floor. The exit location always has at least 50 centimeters between its ceiling and its floor. There is always a way out.

Limits

• $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$

For each test case, output one line containing Case #x: t, where $x$ is the test case number starting from 1, and $t$ is the time in seconds, measured from the moment the tide begins going out, that it takes you to get out of the cave system.

Every event happens at a time that is a whole multiple of 0.1 seconds, so the answer is always a multiple of 0.1. Print $t$ with exactly one digit after the decimal point, and keep that digit even when the value is a whole number.

You may be able to cross the whole cave system before the tide starts dropping. In that case you wait at the exit for the tide to start dropping, so the answer is zero. That is what happens in the fourth test case of the example input.

In the first test case of the example input there are only 33 centimeters between the water level and the ceiling of the eastern square at the start, so once the tide starts going down you have to wait 1.7 seconds before you can enter it. By then the water in the western square is only 3 centimeters above the floor, so you have to drag the kayak for the next 10 seconds to reach the exit.

The second test case starts out better. There is a lot of headroom in the adjacent squares, so you can move to $(1, 1)$ before the tide starts dropping. From there you wait one second for the water level to fall to 90 centimeters, then you kayak south and then east and get out, three seconds in total. You cannot pass through the cave at $(2, 1)$ even though its ceiling is high enough, because there are only 10 centimeters between the floor of that cave and the ceiling of each cave you could enter it from, $(1, 1)$ and $(2, 0)$.

The third test case is similar to the first. You wait at the starting position until the water level falls to 50 centimeters. After that you can kayak toward the exit, but after three moves, which take three seconds, the water is at 20 centimeters, only 10 centimeters above the floor, so the fourth move is a drag instead of a paddle.