题目描述

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 以最优顺序进行切割时能获得的最大可能金币数。

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

Case #1: 5
Case #2: 7
Case #3: 1

提示

在样例 $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 完成