Problem
Where roads intersect, there are often traffic lights that tell pedestrians (people walking) when they should cross the street. A clever pedestrian may try to optimize her path through a city based on when those lights turn green.
The city in this problem is a grid, N rows tall by M columns wide. Our pedestrian wants to get from the northeast corner of the southwest block to the southwest corner of the northeast block. Your objective is to help her find her way from corner to corner in the fastest way possible.
The pedestrian can cross a street in 1 minute, but only if the traffic light is green for the entire crossing. The pedestrian can move between two streets, along one edge of a block, in 2 minutes. The pedestrian can only move along the edges of the block; she cannot move diagonally from one corner of a block to the opposite corner.
Traffic lights follow the following pattern: at intersection i, the northsouth lights stay green for S_{i} minutes, while the eastwest lights stay red. Then the northsouth lights turn red, the eastwest lights turn green, and they stay that way for W_{i} minutes. Then they start the same cycle again. The pedestrian starts moving at t=0 minutes; traffic light i starts a cycle by turning green in the northsouth direction at t=T_{i} minutes. There are cycles before t=T_{i} as well.
For example, intersection 0 could have the following values:
S_{0} = 3, W_{0} = 2, T_{0} = 0
The northsouth direction turns green after 0 minutes. That lasts 3 minutes, during which time the pedestrian can cross in the northsouth direction and not the eastwest direction. Then the lights switch, and for the next 2 minutes the pedestrian can cross in the eastwest direction and not the northsouth direction. Then, 5 minutes after it started, the cycle starts again. This is exactly the same as the following configuration:
S_{0} = 3, W_{0} = 2, T_{0} = 10
Input
The first line in the input contains the number of test cases, C. This is followed by C test cases in the following format:
A single line containing "N M", where N and M are the number of horizontal roads (rows) and vertical roads (columns), as above. This is followed by N lines. The ith of those lines contains information about intersections on the ith row, where the 0th row is the northmost. Each of those lines will contain 3M integers, separated by spaces, in the following form:
S_{i,0} W_{i,0} T_{i,0} S_{i,1} W_{i,1} T_{i,1}... S_{i,M1} W_{i,M1} T_{i,M1}
S_{i,j}, W_{i,j} and T_{i,j} all refer to the intersection in the ith row from the north and the jth column from the west.
Output
For each test case, output a single line containing the text "Case #x: t", where x is the number of the test case and t is the minimum number of minutes it takes the pedestrian to get from the southwest corner to the northeast corner.
Limits
C, N, M, S_{i,j}, W_{i,j}, T_{i,j} are all nonnegative integers.Small Input
1 ≤ N, M ≤ 3Large Input
1 ≤ N, M ≤ 20Sample
Input 
Output 
2

Case #1: 4

Explanation
The first case is described above. 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 case is depicted 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 a block (2 minutes) and crosses to the East (1 minute) for a total of 7 minutes.
Points  Correct  Attempted 

13pt  213  429 
20pt  172  239 