#213616. [GCJ 2008 Finals] Mine Layer

MineLayer is a MineSweeper-like puzzle game played on an by grid. Each square in the grid either has one mine or no mines at all. A MineLayer puzzle consists of a grid of numbers, each of which indicates the total number of mines in all adjacent squares and in the square underneath. The numbers will thus range from zero to nine.

The objective of MineLayer is to figure out a layout of the mines in the grid that matches the given clues.

Below is a typical by grid. The original layout is on the left, and the puzzle on the right.

Since there may be many solutions, your task is to write a program that outputs the maximum possible number of mines in the middle row. The number of rows will always be odd, and there will always be at least one solution to the puzzle.

The first line of input gives the number of cases, . test cases follow.

The first line of each case contains two space-separated numbers: , the number of rows, and , the number of columns. is always an odd integer. Each of the next lines contains space-separated numbers that denote the clues of that row.

For each test case, output one line containing "Case #: ", where is the 1-based case number, and is the maximum possible number of mines in the middle row of a grid that satisfies the given constraints.

样例输入 1

2
3 3
2 2 1
3 4 3
2 3 2
3 4
1 2 1 1
2 3 3 2
2 2 2 1

样例输出 1

Case #1: 1
Case #2: 1

Limits

• .
• Each puzzle is guaranteed to have at least one solution.

Small dataset (4 Pts, Test set 1 - Visible)

• or .
• .

Large dataset (13 Pts, Test set 2 - Hidden)

• is an odd number between and , inclusive.
• .