Crossing the Road (Large)

The city in this problem is a grid made of $N$ roads running east to west and $M$ roads running north to south. There is an intersection wherever an east-west road meets a north-south road, and every intersection has pedestrian lights. A pedestrian can cross a road only in the direction that has a green light.

Intersections are numbered from row $0$ to row $N-1$ going from north to south, and from column $0$ to column $M-1$ going from west to east.

The pedestrian wants to get from the northeast corner of the southwest block to the southwest corner of the northeast block. She starts at the southwest corner of intersection $(N-1, 0)$ and finishes at the northeast corner of intersection $(0, M-1)$.

Two moves are available.

• Cross a road at one intersection, moving to a corner that is not diagonally opposite. This takes 1 minute, and the light for the direction she is crossing must stay green for that entire minute. Crossing in the north-south direction needs the north-south light to be green, and crossing in the east-west direction needs the east-west light to be green.
• Walk along one edge of a block to a corner of a neighboring intersection. This takes 2 minutes.

The pedestrian moves only along the edges of the blocks. She cannot go straight from one corner of a block to the opposite corner. She can wait at a corner as long as she likes.

Traffic lights repeat the following cycle. 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 lights at intersection $i$ start a cycle by turning green in the north-south direction at $t=T_i$ minutes. The same cycle repeats before $t=T_i$ as well.

For example, suppose one intersection has $S_0 = 3$, $W_0 = 2$, $T_0 = 0$. The north-south direction turns green at 0 minutes and stays green for 3 minutes, so during that time the pedestrian can cross in the north-south direction and not in the east-west direction. 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 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 in the format below.

The first line of a test case contains $N$ and $M$, the number of east-west roads (rows) and the number of north-south roads (columns). Then $N$ lines follow. The $i$th of those lines describes the intersections in row $i$ counted from the north, where row 0 is the northmost, and 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}\ \dots\ S_{i,M-1}\ W_{i,M-1}\ T_{i,M-1}$

$S_{i,j}$, $W_{i,j}$ and $T_{i,j}$ refer to the intersection in row $i$ from the north and column $j$ 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 20$
• $0 < S_{i,j}, W_{i,j} \le 10^7$
• $0 \le T_{i,j} \le 10^8$

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

In the first test case of the first example, the lights are the ones described in the statement. The pedestrian crosses to the north (1 minute), waits 2 minutes and then crosses to the east (1 minute), for a total of 4 minutes.

The second test case is shown in the diagram 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 (1 minute), for a total of 7 minutes.