Tại các giao lộ, thường có đèn giao thông báo cho người đi bộ biết khi nào họ nên băng qua đường. Một người đi bộ thông minh có thể cố gắng tối ưu hóa lộ trình của mình qua thành phố dựa trên thời điểm các đèn giao thông chuyển sang màu xanh.

Thành phố trong bài toán này là một lưới gồm \(N\) hàng và \(M\) cột các khối nhà. Người đi bộ của chúng ta muốn đi từ góc đông bắc của khối nhà phía tây nam đến góc tây nam của khối nhà phía đông bắc. Mục tiêu của bạn là giúp cô ấy tìm đường từ góc này sang góc kia trong thời gian nhanh nhất có thể.

Người đi bộ có thể băng qua đường trong 1 phút, nhưng chỉ khi đèn giao thông có màu xanh trong suốt toàn bộ quá trình băng qua. Người đi bộ có thể di chuyển giữa hai con đường, dọc theo một cạnh của khối nhà, trong 2 phút. Người đi bộ chỉ có thể di chuyển dọc theo các cạnh của khối nhà; cô ấy không thể di chuyển theo đường chéo từ góc này sang góc đối diện của một khối nhà.

Đèn giao thông tuân theo quy luật sau: tại giao lộ \(i\), đèn hướng bắc-nam giữ màu xanh trong \(S_i\) phút, trong khi đèn hướng đông-tây giữ màu đỏ. Sau đó, đèn bắc-nam chuyển sang màu đỏ, đèn đông-tây chuyển sang màu xanh và giữ như vậy trong \(W_i\) phút. Sau đó, chúng bắt đầu lại chu kỳ tương tự. Người đi bộ bắt đầu di chuyển tại thời điểm \(t=0\) phút; đèn giao thông \(i\) bắt đầu một chu kỳ bằng cách chuyển sang màu xanh theo hướng bắc-nam tại thời điểm \(t=T_i\) phút. Cũng có các chu kỳ trước thời điểm \(t=T_i\).

Ví dụ, giao lộ 0 có thể có các giá trị sau:
S_0 = 3, W_0 = 2, T_0 = 0

Hướng bắc-nam chuyển sang màu xanh sau 0 phút. Trạng thái đó kéo dài 3 phút, trong thời gian đó người đi bộ có thể băng qua theo hướng bắc-nam chứ không phải hướng đông-tây. Sau đó đèn chuyển đổi, và trong 2 phút tiếp theo, người đi bộ có thể băng qua theo hướng đông-tây chứ không phải hướng bắc-nam. Sau đó, 5 phút kể từ khi bắt đầu, chu kỳ lại bắt đầu. Điều này hoàn toàn giống với cấu hình sau:
S_0 = 3, W_0 = 2, T_0 = 10

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa số lượng bộ thử nghiệm, \(C\). Tiếp theo là \(C\) bộ thử nghiệm theo định dạng sau:

Một dòng duy nhất chứa "\(N\) \(M\)", trong đó \(N\) và \(M\) lần lượt là số lượng đường ngang (hàng) và đường dọc (cột), như đã mô tả ở trên. Tiếp theo là \(N\) dòng. Dòng thứ \(i\) chứa thông tin về các giao lộ trên hàng thứ \(i\), với hàng thứ 0 là hàng ở cực bắc. Mỗi dòng đó sẽ chứa \(3M\) số nguyên, cách nhau bởi dấu cách, dưới dạng:

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}\) và \(T_{i,j}\) đều đề cập đến giao lộ ở hàng thứ \(i\) tính từ phía bắc và cột thứ \(j\) tính từ phía tây.

Dữ liệu ra

Với mỗi bộ thử nghiệm, hãy xuất một dòng duy nhất chứa văn bản "Case #x: t", trong đó x là số thứ tự của bộ thử nghiệm và t là số phút tối thiểu để người đi bộ đi từ góc tây nam đến góc đông bắc.

Ràng buộc

• \(C, N, M, S_{i,j}, W_{i,j}, T_{i,j}\) đều là các số nguyên không âm.
• \(C \le 100\)

Phân nhóm

• Small Input: \(1 \le N, M \le 3\); \(0 < S_{i,j}, W_{i,j} \le 10\); \(0 \le T_{i,j} \le 20\).
• Large Input: \(1 \le N, M \le 20\); \(0 < S_{i,j}, W_{i,j} \le 10^7\); \(0 \le T_{i,j} \le 10^8\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
1 1
3 2 10
1 2
1 5 3 1 5 2

Case #1: 4
Case #2: 7

Nguồn

Google Code Jam 2009, Vòng 1A, bài Crossing the Road.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.