Description

你所在的加油站充气泵前的队伍越来越长了！你希望优化流程，帮助顾客更快速地给轮胎、运动球、巨型气球动物等产品充气。

充气泵是自动的：你可以将目标气压设置为特定的帕斯卡数值，将泵连接到充气产品上，它就会按需充气到该精确气压。泵上只有两个按钮：上和下。它们分别将目标气压精确地增加或减少 $1$ 帕斯卡。

共有 $\mathbf{N}$ 位顾客排队，每位顾客携带恰好 $\mathbf{P}$ 个需要充气的产品。你知道每个产品的目标气压。你可以按任意顺序处理每位顾客的产品，但不能改变顾客的顺序。具体来说，你必须处理完第 $i$ 位顾客的所有产品后，才能开始处理第 $(i+1)$ 位顾客的产品。在处理两个产品之间，如果它们的目标气压不同，你需要使用泵上的按钮调整气压。

充气泵初始气压为 0 帕斯卡，处理完所有顾客的所有产品后可以停留在任意气压值。如果你能优化每位顾客的产品处理顺序，最少需要按下多少次按钮？

Input Format

输入的第一行包含测试用例的数量 $\mathbf{T}$。随后是 $\mathbf{T}$ 个测试用例。每个测试用例的第一行包含两个整数 $\mathbf{N}$ 和 $\mathbf{P}$，分别表示顾客的数量和每位顾客携带的产品数量。接下来是 $\mathbf{N}$ 行，第 $i$ 行包含 $\mathbf{P}$ 个整数 $\mathbf{X}_{\mathbf{i}, 1}, \mathbf{X}_{\mathbf{i}, 2}, \ldots, \mathbf{X}_{\mathbf{i}, \mathbf{P}}$，表示第 $i$ 位顾客的第 $j$ 个产品的目标气压为 $\mathbf{X}_{\mathbf{i}, \mathbf{j}}$ 帕斯卡。

Output Format

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是按照指定气压充气所有产品所需的最少按钮按压次数。

2
3 3
30 10 40
20 50 60
60 60 50
5 2
1 1000000000
500000000 1000000000
1 1000000000
500000000 1
1 1000000000

Case #1: 110
Case #2: 4999999996

Hint

样例解释

在样例 #1 中，一种最优的充气方式是：

1. 按 上 按钮 10 次，将气压设为 10；为顾客 1 的气压需求为 10 的产品充气，
2. 按 上 按钮 30 次，将气压设为 40；为顾客 1 的气压需求为 40 的产品充气，
3. 按 下 按钮 10 次，将气压设为 30；为顾客 1 的气压需求为 30 的产品充气，
4. 按 下 按钮 10 次，将气压设为 20；为顾客 2 的气压需求为 20 的产品充气，
5. 按 上 按钮 30 次，将气压设为 50；为顾客 2 的气压需求为 50 的产品充气，
6. 按 上 按钮 10 次，将气压设为 60；为顾客 2 和顾客 3 的气压需求为 60 的三个产品充气，
7. 最后按 下 按钮 10 次，将气压设为 50；为顾客 3 的气压需求为 50 的产品充气。

总计需要 110 次按钮按压。

在样例 #2 中，请注意答案可能超过 $2^{32}$。

数据范围

• $1 \leq \mathbf{T} \leq 100$。
• $1 \leq \mathbf{X}_{\mathbf{i}, \mathbf{j}} \leq 10^9$（对所有 $i, j$ 成立）。

测试集 1（14 分，可见判定）

• $2 \leq \mathbf{N} \leq 10$。
• $2 \leq \mathbf{P} \leq 3$。

测试集 2（21 分，隐藏判定）

• $2 \leq \mathbf{N} \leq 1000$。
• $2 \leq \mathbf{P} \leq 100$。

翻译由 DeepSeek V3 完成