길 건너기 (라지)

이 문제의 도시는 동서로 놓인 도로 $N$개와 남북으로 놓인 도로 $M$개가 만드는 격자다. 동서 도로와 남북 도로가 만나는 곳마다 교차로가 있고, 교차로마다 보행자 신호등이 있다. 보행자는 초록불인 방향으로만 길을 건널 수 있다.

교차로는 북쪽에서 남쪽으로 $0$번 행부터 $N-1$번 행까지, 서쪽에서 동쪽으로 $0$번 열부터 $M-1$번 열까지 번호를 붙인다.

보행자는 남서쪽 블록의 북동쪽 모퉁이에서 출발해 북동쪽 블록의 남서쪽 모퉁이까지 가려고 한다. 즉 출발점은 교차로 $(N-1, 0)$의 남서쪽 모퉁이이고, 목적지는 교차로 $(0, M-1)$의 북동쪽 모퉁이다.

보행자가 할 수 있는 이동은 두 가지다.

• 한 교차로에서 길을 건너 대각선이 아닌 다른 모퉁이로 간다. 1분이 걸리고, 건너는 그 1분 내내 건너는 방향의 신호가 초록불이어야 한다. 남북 방향으로 건너려면 남북 신호가, 동서 방향으로 건너려면 동서 신호가 초록불이어야 한다.
• 블록의 한 변을 따라 이웃한 교차로의 모퉁이까지 걸어간다. 2분이 걸린다.

보행자는 블록의 변 위에서만 움직인다. 블록의 한 모퉁이에서 대각선 반대쪽 모퉁이로 바로 갈 수는 없다. 모퉁이에서는 원하는 만큼 기다릴 수 있다.

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

예를 들어 어떤 교차로의 값이 $S_0 = 3$, $W_0 = 2$, $T_0 = 0$이라고 하자. 0분에 남북 방향이 초록불로 바뀌어 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}\ \dots\ 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 20$
• $0 < S_{i,j}, W_{i,j} \le 10^7$
• $0 \le T_{i,j} \le 10^8$

각 테스트 케이스마다 한 줄에 Case #x: t를 출력한다. $x$는 테스트 케이스의 번호이고, $t$는 보행자가 출발점에서 목적지까지 가는 데 걸리는 최소 시간(분)이다.

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

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