题目描述

Gridtopia 城市是一个由 $R$ 行 $C$ 列方格（“街区”）组成的矩阵。行号从上到下编号（从 1 开始），列号从左到右编号（从 1 开始）。城市中有 $S$ 个不同的警察局，第 $i$ 个警察局位于第 $R_i$ 行第 $C_i$ 列的街区，并且每个街区最多只包含一个警察局。

每个警察局只能巡逻距离其自身不超过 $D_i$ 个街区的区域（横向或纵向）。也就是说，第 $i$ 个警察局只能巡逻第 $R'$ 行第 $C'$ 列的街区，当且仅当 $\max(|R' - R_i|, |C' - C_i|) \leq D_i$。换句话说，第 $i$ 个警察局只能巡逻以其为中心、边长为 $2D_i + 1$ 的正方形范围内的街区。

作为新任警察局长，你需要将城市中的部分街区分配给能够巡逻它们的某一个警察局，并且每个街区只能分配给一个警察局。包含警察局的街区以及没有任何警察局能够巡逻到的街区不需要分配。其他所有街区都必须被分配。此外，你还需要尽可能均匀地分配这些任务。设 $A_i$ 表示分配给第 $i$ 个警察局的街区数，你的目标是最小化所有 $A_i$ 的最大值与最小值之差。如果你采用最优分配方案，这个最小可能的差值是多少？

输入格式

输入的第一行是测试用例数 $T$。接下来有 $T$ 组测试数据。每组数据的第一行为三个整数 $R$、$C$ 和 $S$，分别表示城市的行数、列数和警察局数量。接下来的 $S$ 行，每行三个整数 $R_i$、$C_i$ 和 $D_i$，分别表示第 $i$ 个警察局所在的行、列，以及该警察局能够巡逻的最大距离参数，如上所述。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是上述最小差值。

输入输出样例 #1

输入 #1

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

输出 #1

Case #1: 4
Case #2: 0

说明/提示

在样例 1 中，城市为 $3$ 行 $4$ 列的网格，一个警察局在左上角，一个警察局在右下角左侧的街区。第一个警察局只能巡逻与其相邻的三个街区，其他街区距离它的横向或纵向距离都超过 1。第二个警察局可以巡逻除警察局所在街区外的所有街区。如果将第一个警察局能巡逻的三个街区都分配给它，剩下的七个街区分配给第二个警察局，则分配的最大最小差值最小。

在样例 2 中，一种最优分配方式如下图所示。图中 $1$ 表示第 1 个警察局，$2$ 表示第 2 个警察局，$!$ 表示分配给第 1 个警察局的街区，$@$ 表示分配给第 2 个警察局的街区，$.$ 表示没有分配给任何警察局（因为没有警察局能巡逻到）。注意，一个警察局分配到的街区不需要连成一片。

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

数据范围

• $1 \leq T \leq 100$。
• $2 \leq S \leq 15$。
• $1 \leq R_i \leq R$，对所有 $i$。
• $1 \leq C_i \leq C$，对所有 $i$。
• 对所有 $i \neq j$，$R_i \neq R_j$ 或 $C_i \neq C_j$（即没有两个警察局在同一个街区）。
• $1 \leq D_i < \max(R, C)$，对所有 $i$。

测试点 1（5 分，可见）

• $1 \leq R \leq 20$。
• $1 \leq C \leq 20$。

测试点 2（23 分，隐藏）

• $1 \leq R \leq 10^9$。
• $1 \leq C \leq 10^9$。