길 건너기 (작은 입력)

도로가 교차하는 곳에는 보행자가 언제 길을 건널 수 있는지 알려 주는 신호등이 있다. 영리한 보행자는 신호가 초록불로 바뀌는 시각에 맞춰 도시를 지나는 경로를 짠다.

이 문제의 도시는 동서로 뻗은 도로 $N$개와 남북으로 뻗은 도로 $M$개가 만드는 격자다. 교차로는 모두 $N \times M$개다. 보행자는 남서쪽 블록의 북동쪽 모서리에서 출발해 북동쪽 블록의 남서쪽 모서리까지 가려고 한다. 다시 말해 가장 남서쪽 교차로의 남서쪽 모서리에서 출발해 가장 북동쪽 교차로의 북동쪽 모서리에 도착한다. 출발 모서리에서 도착 모서리까지 걸리는 최소 시간을 구하라.

도로 하나를 건너는 데는 1분이 걸리고, 건너는 1분 동안 그 방향 신호가 내내 초록불이어야 한다. 교차로마다 모서리가 네 개 있고, 도로를 한 번 건너면 같은 교차로의 이웃한 모서리로 옮겨 간다. 블록의 한 변을 따라 이웃한 두 교차로 사이를 걷는 데는 2분이 걸리고, 이때는 신호와 무관하다. 보행자는 블록의 변을 따라서만 움직이며, 블록의 한 모서리에서 마주 보는 모서리로 대각선으로 가로지르지는 못한다.

신호등은 다음 규칙을 따른다. 교차로 $i$에서 남북 방향 신호가 $S_i$분 동안 초록불이고, 그동안 동서 방향 신호는 빨간불이다. 이어서 남북 방향이 빨간불로, 동서 방향이 초록불로 바뀌어 $W_i$분 동안 유지된다. 그다음 같은 주기가 처음부터 반복된다. 보행자는 $t=0$분에 움직이기 시작하고, 교차로 $i$의 주기는 $t=T_i$분에 남북 방향이 초록불로 바뀌면서 시작한다. $t=T_i$ 이전에도 같은 주기가 계속 반복되고 있다.

예를 들어 교차로 0의 값이 $S_0 = 3$, $W_0 = 2$, $T_0 = 0$이라고 하자. 0분에 남북 방향이 초록불이 되어 3분 동안 유지되고, 그 3분 동안 보행자는 남북 방향으로만 건널 수 있다. 그다음 신호가 바뀌어 2분 동안은 동서 방향으로만 건널 수 있다. 주기가 시작된 지 5분 뒤에 같은 주기가 다시 시작된다. 이 설정은 $S_0 = 3$, $W_0 = 2$, $T_0 = 10$과 완전히 같다.

첫 줄에 테스트 케이스의 수 $C$가 주어진다. 이어서 $C$개의 테스트 케이스가 다음 형식으로 주어진다.

각 테스트 케이스의 첫 줄에 동서 방향 도로의 수 $N$과 남북 방향 도로의 수 $M$이 공백으로 구분되어 주어진다. 이어지는 $N$개의 줄 중 $i$번째 줄은 북쪽에서 $i$번째 행에 있는 교차로의 정보를 담는다. 가장 북쪽 행이 0번째 행이다. 각 줄에는 정수 $3M$개가 공백으로 구분되어 다음 순서로 주어진다.

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}$, $T_{i,j}$는 북쪽에서 $i$번째 행, 서쪽에서 $j$번째 열에 있는 교차로의 값이다.

제한

• $C$, $N$, $M$, $S_{i,j}$, $W_{i,j}$, $T_{i,j}$는 모두 음이 아닌 정수다.
• $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$

각 테스트 케이스마다 Case #x: t 형식으로 한 줄씩 출력한다. $x$는 테스트 케이스 번호이고, $t$는 보행자가 출발 모서리에서 도착 모서리까지 가는 데 걸리는 최소 시간(분)이다.

첫 번째 예제의 첫 케이스는 위에서 설명한 신호 설정과 같다. 보행자는 북쪽으로 건너고(1분), 2분을 기다린 뒤 동쪽으로 건넌다(1분). 모두 4분이다.

둘째 케이스는 아래 그림과 같다. 보행자는 동쪽으로 건너고(1분), 2분을 기다린 뒤 북쪽으로 건넌다(1분). 그다음 동쪽으로 한 블록을 걸어가고(2분) 다시 동쪽으로 건너서(1분) 모두 7분이 걸린다.