P13055 [GCJ 2020 #1A] Square Dance

你正在组织一场国际舞蹈比赛。目前已经准备好以下内容： * 一个由 $\mathbf{R}$ 行 $\mathbf{C}$ 列单位方格组成的舞池； * $\mathbf{R} \times \mathbf{C}$ 名参赛选手； * 一套先进的自动评分系统。 但你还缺少观众！担心比赛可能不够精彩，你设计了一种计算比赛**精彩度**的方法。 每名选手占据舞池的一个单位方格，直到被淘汰为止。选手 $\mathrm{x}$ 的**罗盘邻居**是指满足以下条件的另一选手 $\mathrm{y}$：$\mathrm{y}$ 与 $\mathrm{x}$ 同行或同列，且 $\mathrm{x}$ 与 $\mathrm{y}$ 之间没有其他未被淘汰的选手。每名选手可能有 0 到 4 个罗盘邻居（包含边界），且数量会因某一方向上选手被淘汰而减少。 比赛按轮次进行。在第 $\mathrm{i}$ 轮和第 $\mathrm{i}+1$ 轮之间，若选手 $\mathrm{d}$ 在第 $\mathrm{i}$ 轮时有至少一个罗盘邻居，且 $\mathrm{d}$ 的技能值**严格小于**其所有罗盘邻居技能值的平均值，则 $\mathrm{d}$ 被淘汰，不再参与后续轮次。注意：$\mathrm{d}$ 在被淘汰前仍会作为其他选手的罗盘邻居参与淘汰判定。没有罗盘邻居的选手永远不会被淘汰。若某一轮后无人被淘汰，则比赛结束。 每一轮的精彩度是该轮所有参赛选手（包括即将被淘汰者）技能值之和。比赛的**总精彩度**是所有轮次精彩度的总和。 给定第一轮所有选手的技能值，求比赛的总精彩度。

输入第一行包含测试用例数量 $\mathrm{T}$。随后是 $\mathrm{T}$ 个测试用例，每个用例格式如下： - 第一行：两个整数 $\mathbf{R}$ 和 $\mathbf{C}$； - 接下来 $\mathbf{R}$ 行：每行 $\mathbf{C}$ 个整数，其中第 $\mathrm{i}$ 行第 $\mathrm{j}$ 列的 $\mathrm{S}_{\mathrm{i}, \mathrm{j}}$ 表示初始位于第 $\mathrm{i}$ 行第 $\mathrm{j}$ 列选手的技能值。

对于每个测试用例，输出一行 `Case #x: y`，其中 $\mathrm{x}$ 为测试用例编号（从 1 开始），$\mathrm{y}$ 为比赛的总精彩度。

**样例解释** - **样例 #1**：仅有一名选手。因其无罗盘邻居，比赛仅进行一轮，总精彩度为该选手技能值 15。 - **样例 #2**： - 第一轮精彩度：$1+1+1+1+2+1+1+1+1=10$。 - 非中心且非角落的选手（技能值 1）因邻居平均值 $4/3 > 1$ 被淘汰。第二轮舞池如下： ``` 1 . 1 . 2 . 1 . 1 ``` - 角落选手的邻居平均值等于自身技能值，中心选手无邻居，比赛结束。第二轮精彩度 $1+1+2+1+1=6$，总精彩度 $10+6=16$。 - **样例 #3**： - 第一轮后技能值 1 的选手被淘汰，剩余两人。 - 第二轮中，技能值 2 的选手因邻居平均值 $3/1 > 2$ 被淘汰。 - 第三轮仅剩一人，比赛结束。各轮精彩度分别为 6、5、3，总精彩度 14。 **数据范围** - $\forall i,j$，$1 \leqslant S_{i, j} \leqslant 10^{6}$。 **测试集 1（9 分，可见评测结果）** - $1 \leqslant \mathrm{T} \leqslant 100$； - $1 \leqslant \mathrm{R} \times \mathrm{C} \leqslant 100$。 **测试集 2（28 分，隐藏评测结果）** - $10 \leqslant \mathrm{T} \leqslant 100$； - 恰好 10 个用例满足 $1000 < \mathrm{R} \times \mathrm{C} \leqslant 10^{5}$； - 其余 $\mathrm{T}-10$ 个用例满足 $1 \leqslant \mathrm{R} \times \mathrm{C} \leqslant 1000$。 翻译由 DeepSeek V3 完成