P16636 [GKS 2017 #G] Matrix Cutting

Shekhu 教授有一个 $N$ 行 $M$ 列的矩阵，行从上到下编号为 $0$ 到 $N-1$，列从左到右编号为 $0$ 到 $M-1$。矩阵的每个格子包含一个正整数。 他希望通过水平切割和垂直切割，将这个矩阵切成 $N \times M$ 个子矩阵（每个大小为 $1 \times 1$）。切割只能在两行或两列之间的边界上进行。 Shekhu 教授邀请他最好的学生 Akki 来完成这项工作，并提出了一个有趣的方案。每次 Akki 在一个子矩阵上进行切割之前，他会获得与该子矩阵中最小值相等数量的金币。注意，每次切割会使子矩阵的总数增加。此外，在不同子矩阵中的切割是相互独立的，Akki 在不同子矩阵中的切割所获得的金币也是独立计算的。 现在，Akki 有多种方式进行切割。你能帮助他最大化他能获得的金币总数吗？

输入的第一行包含一个整数 $T$，表示测试用例的数量。接下来有 $T$ 个测试用例。 每个测试用例的第一行包含两个整数 $N$ 和 $M$，含义如上所述。 接下来有 $N$ 行，每行包含 $M$ 个正整数，描述矩阵。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 Akki 以最优顺序进行切割时能获得的最大可能金币数。

在样例 $1$ 中，Akki 有两种可能的切割方式。 1. 假设 Akki 先水平切割矩阵。他获得矩阵中的最小值 $1$ 个金币。然后他需要在两个子矩阵（$[1, 2]$ 和 $[3, 4]$）中进行垂直切割，分别获得 $1$ 和 $3$ 个金币。 2. 假设 Akki 先垂直切割矩阵。他获得矩阵中的最小值 $1$ 个金币。然后他需要在两个子矩阵（其转置为 $[1, 3]$ 和 $[2, 4]$）中进行水平切割，分别获得 $1$ 和 $2$ 个金币。 第一种策略更好，答案为 $5$。 在样例 $2$ 中，Akki 最多可以获得 $7$ 个金币。一种最优方式是：先进行唯一的水平切割，获得 $1$ 个金币。然后，在上子矩阵 $[1, 2, 1]$ 中，Akki 可以先在第一列右侧立即切割，再在第二列右侧立即切割，共获得 $2$ 个金币。类似地，在下子矩阵 $[2, 3, 2]$ 中，Akki 可以先在第二列右侧立即切割，再在第一列右侧立即切割，共获得 $4$ 个金币。 在样例 $3$ 中，只需要进行一次切割。 ### 限制条件 $1 \le T \le 100$。 矩阵中的每个值 $\le 10^5$。 **小数据集（测试集 1 – 可见）** $N = 1$。 $1 \le M \le 10$。 **大数据集（测试集 2 – 隐藏）** $1 \le N \le 40$。 $1 \le M \le 40$。 翻译由 DeepSeek V4 Pro 完成