P12986 [GCJ 2022 #1A] Weightlifting

你正在按照一套举重训练计划进行训练。该训练由一系列必须按顺序完成的动作组成，每个动作需要在器械上放置特定的配重组合。 共有 $\mathbf{W}$ 种不同类型的配重。例如，某个动作可能需要 3 个 A 型配重和 1 个 B 型配重，而下一个动作可能需要 2 个 A 型、2 个 C 型和 2 个 D 型配重。  配重以**堆栈**形式放置在器械上。每次操作你可以： - 将任意类型的新配重添加到堆栈顶部 - 或移除当前位于堆栈顶部的配重 每个动作所需的配重可以按任意顺序装载。例如，若在第一个动作中将 B 型配重放在最底层，那么在装载第二个动作的配重前需要清空所有配重；但若将 B 型配重放在倒数第三层，则可保留底部的两个 A 型配重用于下一个动作，从而减少操作次数。 给定每个动作所需的各类配重数量，计算完成所有训练所需的最少操作次数。训练必须按给定顺序完成，器械堆栈初始为空，训练结束后也必须恢复为空栈。

第一行输入测试用例数量 $\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$ 型配重。

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

**样例解释** 样例 #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 完成