P16730 [GKS 2019 #C] Circuit Board

Arsh 最近发现了一块旧的矩形电路板，想要回收利用。该电路板有 $R$ 行 $C$ 列方格。 电路板的每个方格都有一个厚度（单位为毫米）。第 $r$ 行第 $c$ 列的方格厚度为 $V_{r,c}$。如果每一行中，最厚方格与最薄方格的厚度差不超过 $K$，则称该电路板是 **好的**。 由于原始电路板可能不是好的，Arsh 想从中找出一个好的子电路板。子电路板可以通过从原始板中选取一个与坐标轴对齐的子矩形，并取该子矩形内的所有方格得到。Arsh 希望你能帮助他找出原始板中最大的好子矩形所含的方格数。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含三个整数 $R$、$C$ 和 $K$，分别表示行数、列数以及每行允许的最大厚度差。 随后 $R$ 行，每行包含 $C$ 个整数。第 $r$ 行的第 $c$ 个整数为 $V_{r,\, c}$，表示第 $r$ 行第 $c$ 列方格的厚度。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是一个好的子矩形中所包含的最大方格数。

### 额外样例 – 测试集 2 以下样例说明了各测试用例的情况。对于每个测试用例，包含最多方格的好子电路板用绿色高亮显示。 :::align{center}  ::: ### 限制条件 $1 \le T \le 50$。 $1 \le R \le 300$。 $1 \le C \le 300$。 对于所有 $i, j$，$0 \le V_{i,\,j} \le 10^3$。 **测试集 1（可见）** $K = 0$。 **测试集 2（隐藏）** $0 \le K \le 10^3$。 翻译由 DeepSeek V4 Pro 完成