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, rows tall by 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 , the north-south lights stay green for minutes, while the east-west lights stay red. Then the north-south lights turn red, the east-west lights turn green, and they stay that way for 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 north-south direction at minutes. There are cycles before as well.
For example, intersection 0 could have the following values:
The north-south direction turns green after 0 minutes. That lasts 3 minutes, during which time the pedestrian can cross in the north-south direction and not the east-west direction. Then the lights switch, and for the next 2 minutes the pedestrian can cross in the east-west direction and not the north-south direction. Then, 5 minutes after it started, the cycle starts again. This is exactly the same as the following configuration:
The first line in the input contains the number of test cases, . This is followed by test cases in the following format:
A single line containing
N M, where and are the number of horizontal roads (rows) and vertical roads (columns), as above. This is followed by lines. The of those lines contains information about intersections on the row, where the row is the northmost. Each of those lines will contain integers, separated by spaces, in the following form:
, and all refer to the intersection in the row from the north and the column from the west.
For each test case, output a single line containing the text
Case #x: t, where is the number of the test case and is the minimum number of minutes it takes the pedestrian to get from the southwest corner to the northeast corner.
Time limit: 30 seconds per test set.
Memory limit: 1 GB.
, , , , , are all non-negative integers.
2 1 1 3 2 10 1 2 1 5 3 1 5 2
Case #1: 4 Case #2: 7
Explanation for Sample
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.