Tide Goes In, Tide Goes Out (Small)

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 are stuck 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 tide starts going out.

The cave system is an $N$ by $M$ grid. Your map consists of two $N$ by $M$ grids of numbers: one gives the height of the ceiling in each grid square, and the other gives the height of the floor in each grid square. The floor of the cave system is porous, so as the water level falls, no water remains 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, but 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 under 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 with floor at height 10 centimeters to an adjacent square with floor at height 9000 centimeters, assuming the constraints above are met.

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 start moving from one square to another, if there are at least 20 centimeters of water remaining on the square you are leaving, the move takes 1 second, because you can use your kayak. Otherwise it takes 10 seconds, because you have to drag your kayak. The time depends only on the water depth in the square you are leaving, not in the square you are entering.

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 you have to compute is the time from the moment the water starts going down until the moment you reach the exit.

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

It is followed by $T$ test cases, each starting with a line containing the integers $H$, $N$ and $M$, the initial water level height in centimeters and the map dimensions. The following $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 row $i$ and column $j$. Row numbers increase to the South and column numbers increase to the East.
• The next $N$ lines contain $M$ space-separated integers each, giving the floor heights $F_{ij}$ in the same format.

At the starting location there is always at least 50 cm of air between the ceiling and the starting water level, and at least 50 cm between the ceiling and the floor.

The exit location always has at least 50 cm of air between the ceiling and the floor.

There is always a way out.

Limits

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

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

$t$ is always a multiple of 0.1 seconds, so print it with exactly one digit after the decimal point. For example, write 3 seconds as 3.0 and 11.7 seconds as 11.7.

You may be able to go through the whole cave system before the tide starts dropping. In that case you can wait at the exit for the tide to start dropping, so the answer is zero. This is what happens in the fourth sample case.

In the first sample case there are initially only 33 centimeters between the water level and the ceiling of the eastern square, so after the tide starts going down you have to wait 1.7 seconds to enter it. By the time it is accessible, the water level in the western square is only 3 centimeters above the floor, so you have to drag your kayak for the next 10 seconds to get to the exit.

The initial situation in the second case is better. You have plenty of headroom in adjacent squares, so you can move to row 2, column 2 before the tide starts dropping. Once there you wait one second for the water level to go down to 90 cm, then you kayak south and then east and get out, three seconds in total. You cannot go through the cave at row 2, column 3, even though its ceiling is high enough, because there is only 10 centimeters between the floor of that cave and the ceiling of either cave you could enter it from, row 2 column 2 and row 1 column 3.

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

In the fourth case you can go straight to the exit before the tide starts leaving, and wait there.