Crossing the Road (Small)

Where roads intersect there are traffic lights that tell pedestrians when they may cross. A clever pedestrian plans her route through the city around the moments those lights turn green.

The city in this problem is a grid of $N$ roads running east to west and $M$ roads running north to south, so it has $N \times M$ intersections. The pedestrian wants to get from the northeast corner of the southwest block to the southwest corner of the northeast block. In other words, she starts at the southwest corner of the southwesternmost intersection and finishes at the northeast corner of the northeasternmost intersection. Find the smallest number of minutes she needs to get from the start corner to the goal corner.

Crossing one road takes 1 minute, and the light for that direction must be green for the entire crossing. Every intersection has four corners, and one crossing moves the pedestrian to an adjacent corner of the same intersection. Walking along one edge of a block, between two neighboring intersections, takes 2 minutes and needs no light. The pedestrian moves only along the edges of a block; she cannot cut diagonally from one corner of a block to the opposite corner.

Traffic lights follow this pattern. At intersection $i$ the north-south lights stay green for $S_i$ minutes while the east-west lights stay red. Then the north-south lights turn red, the east-west lights turn green, and they stay that way for $W_i$ minutes. Then the same cycle starts again. The pedestrian starts moving at $t=0$ minutes, and the cycle at intersection $i$ starts by turning green in the north-south direction at $t=T_i$ minutes. The same cycle also repeats before $t=T_i$.

For example, suppose intersection 0 has $S_0 = 3$, $W_0 = 2$, $T_0 = 0$. The north-south direction turns green at minute 0 and stays green for 3 minutes, and during those 3 minutes the pedestrian can cross in the north-south direction only. Then the lights switch, and for the next 2 minutes she can cross in the east-west direction only. Five minutes after it started, the cycle starts again. This configuration is exactly the same as $S_0 = 3$, $W_0 = 2$, $T_0 = 10$.

The first line contains the number of test cases, $C$. Then $C$ test cases follow, each in this format.

The first line of a test case contains $N$ and $M$, the number of east-west roads and the number of north-south roads. Then $N$ lines follow. The $i$th of those lines describes the intersections on the $i$th row from the north, where the northmost row is row 0. Each of those lines contains $3M$ integers separated by spaces, in this order.

S[i][0] W[i][0] T[i][0] S[i][1] W[i][1] T[i][1] ... S[i][M-1] W[i][M-1] T[i][M-1]

$S_{i,j}$, $W_{i,j}$ and $T_{i,j}$ belong to the intersection in the $i$th row from the north and the $j$th column from the west.

Limits

• $C$, $N$, $M$, $S_{i,j}$, $W_{i,j}$ and $T_{i,j}$ are all non-negative integers.
• $C \le 100$
• $1 \le N, M \le 3$
• $0 < S_{i,j}, W_{i,j} \le 10$
• $0 \le T_{i,j} \le 20$

For each test case, output one line containing Case #x: t, where $x$ is the number of the test case and $t$ is the minimum number of minutes the pedestrian needs to get from the start corner to the goal corner.

The first case of the first example uses the light setting described above. The pedestrian crosses to the north (1 minute), waits 2 minutes, then crosses to the east (1 minute), for a total of 4 minutes.

The second case is drawn below. The pedestrian crosses to the east (1 minute), waits 2 minutes and crosses to the north (1 minute). Then she walks east one block (2 minutes) and crosses to the east again (1 minute), for a total of 7 minutes.