길 건너기

도로가 교차하는 곳에는 보행자(걷는 사람)에게 언제 길을 건너야 하는지 알려 주는 신호등이 흔히 있다. 영리한 보행자는 신호등이 언제 초록불로 바뀌는지에 따라 도시를 지나는 경로를 최적화하려 할 수 있다.

이 문제의 도시는 세로 N행, 가로 M열의 격자이다. 보행자는 남서쪽 블록의 북동쪽 모서리에서 북동쪽 블록의 남서쪽 모서리까지 가려고 한다. 보행자가 가능한 한 가장 빠르게 한 모서리에서 다른 모서리로 가는 길을 찾도록 돕는 것이 목표이다.

보행자는 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분 동안 지속되며, 그동안 보행자는 남북 방향으로 건널 수 있지만 동서 방향으로는 건널 수 없다. 그다음 신호가 바뀌고, 이어지는 2분 동안 보행자는 동서 방향으로 건널 수 있지만 남북 방향으로는 건널 수 없다. 이후 시작한 지 5분이 지나면 주기가 다시 시작된다. 이는 다음 설정과 정확히 같다.

$S_{0}$ = 3, $W_{0}$ = 2, $T_{0}$ = 10

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1 GB.

C, N, M, $S_{i,j}$, $W_{i,j}$, $T_{i,j}$는 모두 음이 아닌 정수이다. C ≤ 100

작은 입력

1 ≤ N, M ≤ 3 0 < $S_{i,j}$, $W_{i,j}$ ≤ 10 0 ≤ $T_{i,j}$ ≤ 20

큰 입력

1 ≤ N, M ≤ 20 0 < $S_{i,j}$, $W_{i,j}$ ≤ $10^{7}$ 0 ≤ $T_{i,j}$ ≤ $10^{8}$

입력의 첫 번째 줄에는 테스트 케이스의 수 C가 주어진다. 이어서 다음 형식의 C개 테스트 케이스가 주어진다.

"N M"을 포함하는 한 줄이 주어지며, 위에서 설명한 것처럼 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번째 열에 있는 교차로를 나타낸다.

각 테스트 케이스에 대해 "Case #x: t"라는 텍스트를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이고, t는 보행자가 남서쪽 모서리에서 북동쪽 모서리까지 가는 데 걸리는 최소 시간(분)이다.

설명

첫 번째 케이스는 위에서 설명했다. 보행자는 북쪽으로 건너고(1분), 2분을 기다린 다음 동쪽으로 건너서(1분), 총 4분이 걸린다.

두 번째 케이스는 아래 그림에 나타나 있다. 보행자는 동쪽으로 건너고(1분), 2분을 기다린 다음 북쪽으로 건넌다(1분). 그다음 한 블록을 동쪽으로 걷고(2분), 동쪽으로 건너서(1분), 총 7분이 걸린다.