Jurisdiction Restrictions

The city of Gridtopia is a matrix of square cells ("blocks") with $R$ rows and $C$ columns. Rows are numbered from 1 at the top to $R$ at the bottom, and columns are numbered from 1 at the left to $C$ at the right. The city is served by $S$ police stations. The $i$-th station is in the block at row $R_i$ and column $C_i$. No block contains more than one station.

Each station can only patrol blocks that are no more than $D_i$ blocks away from it, horizontally or vertically. The $i$-th station can patrol the block at row $R'$ and column $C'$ if $\max(|R' - R_i|, |C' - C_i|) \le D_i$. Put another way, the $i$-th station can patrol only the blocks inside the square of side length $2D_i + 1$ centered on that station.

You are the new police commissioner. Assign some blocks to exactly one station that can patrol them. Blocks that contain stations and blocks that no station can patrol are not assigned. Every other block must be assigned. Let $A_i$ be the number of blocks assigned to the $i$-th station. Distribute the load as evenly as possible by minimizing the difference between the maximum and the minimum of all $A_i$ values. What is the smallest possible difference?

The first line contains $T$, the number of test cases. Each case begins with a line containing $R$, $C$, and $S$. Then $S$ lines follow, each with $R_i$, $C_i$, and $D_i$.

For each test case, output one line Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the difference described above.

• $1 \le T \le 100$.
• $2 \le S \le 15$.
• $1 \le R_i \le R$ for all $i$.
• $1 \le C_i \le C$ for all $i$.
• For all $i \ne j$, $R_i \ne R_j$ and/or $C_i \ne C_j$. (No two stations are in the same block.)
• $1 \le D_i < \max(R, C)$ for all $i$.

In Sample Case #1, the city is a grid with 3 rows and 4 columns, with one station in the upper left block and one station in the block to the left of the lower right block. The first station can only patrol the three blocks that touch the edge or corner of its block. Every other block is more than 1 block away horizontally or vertically. The second station can patrol any block in the grid except the blocks containing the stations. The difference in the number of assigned blocks is minimized if station 1 is assigned all three of the blocks it can patrol, and the remaining seven blocks are assigned to station 2.

In Sample Case #2, one optimal strategy is shown below. 1 is station 1, 2 is station 2, ! is a block assigned to station 1, @ is a block assigned to station 2, and . is a block assigned to neither station. A station's assigned blocks do not need to form a single continuous area.

@@@@.
!!!@.
!2!@.
1!!@.
!@!@.