Description

你正在按照一套举重训练计划进行训练。该训练由一系列必须按顺序完成的动作组成，每个动作需要在器械上放置特定的配重组合。

共有 $\mathbf{W}$ 种不同类型的配重。例如，某个动作可能需要 3 个 A 型配重和 1 个 B 型配重，而下一个动作可能需要 2 个 A 型、2 个 C 型和 2 个 D 型配重。

配重以堆栈形式放置在器械上。每次操作你可以：

• 将任意类型的新配重添加到堆栈顶部
• 或移除当前位于堆栈顶部的配重

每个动作所需的配重可以按任意顺序装载。例如，若在第一个动作中将 B 型配重放在最底层，那么在装载第二个动作的配重前需要清空所有配重；但若将 B 型配重放在倒数第三层，则可保留底部的两个 A 型配重用于下一个动作，从而减少操作次数。

给定每个动作所需的各类配重数量，计算完成所有训练所需的最少操作次数。训练必须按给定顺序完成，器械堆栈初始为空，训练结束后也必须恢复为空栈。

Input Format

第一行输入测试用例数量 $\mathbf{T}$。每个测试用例首行包含两个整数 $\mathbf{E}$（动作数量）和 $\mathbf{W}$（配重类型数，编号为 1 到 $\mathbf{W}$）。随后 $\mathbf{E}$ 行中，第 $i$ 行包含 $\mathbf{W}$ 个整数 $\mathbf{X}_{i,1}, \mathbf{X}_{i,2}, \ldots, \mathbf{X}_{i,\mathbf{W}}$，表示第 $i$ 个动作需要 $\mathbf{X}_{i,j}$ 个 $j$ 型配重。

Output Format

对每个测试用例输出 Case #x: y，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为完成所有训练的最少操作次数。

3
3 1
1
2
1
2 3
1 2 1
2 1 2
3 3
3 1 1
3 3 3
2 3 3

Case #1: 4
Case #2: 12
Case #3: 20

Hint

样例解释

样例 #1 仅含 1 种配重类型：

1. 添加 1 个配重（完成第 1 个动作）
2. 再添加 1 个配重（完成第 2 个动作）
3. 移除 1 个配重（完成第 3 个动作）
4. 移除最后 1 个配重（恢复空栈）

样例 #2 的 12 次操作方案：

1. 添加 2 型 → [2]
2. 添加 3 型 → [2,3]
3. 添加 1 型 → [2,3,1]
4. 添加 2 型 → [2,3,1,2]（完成第 1 个动作）
5. 移除 2 型 → [2,3,1]
6. 添加 3 型 → [2,3,1,3]
7. 添加 1 型 → [2,3,1,3,1]（完成第 2 个动作） 8-12. 按 1→3→1→3→2 顺序移除所有配重

限制条件

• $1 \leq \mathbf{T} \leq 100$
• 每个动作至少需要 1 个配重（$\mathbf{X}_{i,1} + \cdots + \mathbf{X}_{i,\mathbf{W}} \geq 1$）

测试集 1（13 分，可见判果）

• $1 \leq \mathbf{E} \leq 10$
• $1 \leq \mathbf{W} \leq 3$
• $0 \leq \mathbf{X}_{i,j} \leq 3$

测试集 2（31 分，隐藏判果）

• $1 \leq \mathbf{E} \leq 100$
• $1 \leq \mathbf{W} \leq 100$
• $0 \leq \mathbf{X}_{i,j} \leq 100$

翻译由 DeepSeek V3 完成