Description

Edythe 是一名年轻的女巫师，在 Merlin, Inc. 的质量保证部门工作——这是一家魔法咒语工厂。她的工作是测试 Merlin 本人发明的魔法咒语。每个咒语都需要精确数量的某些原材料，并将它们转化为其它数量的其他原材料。Edythe 的任务是每个咒语都恰好施放一次，以验证咒语是否正确。

她只有在拥有每种原材料所需数量时才能施放咒语。如果她已经通过之前的咒语创造出了所需类型的原材料，Edythe 必须优先使用这些原材料。然而，如果她仍然需要更多的原材料，她可以从 Merlin 的仓库中取用。她一开始没有任何原材料，但在最后，她可以保留所有自己创造且未使用的多余原材料。

Edythe 希望能通过学徒期赚取尽可能多的利润！她必须恰好施放给定的 $\mathrm{N}$ 个咒语各一次，但可以以任意顺序进行。假设每个咒语都如预期般工作，哪种施放顺序能让她最终获得最多的金钱呢？

例如，假设测试计划包含以下 3 个咒语：

1. 输入：价值 $ $7$ 的黄金。输出：价值 $ $5$ 的硫磺。
2. 输入：无。输出：价值 $ $10$ 的黄金，价值 $ $10$ 的硫磺。
3. 输入：价值 $ $3$ 的黄金，价值 $ $20$ 的硫磺。输出：价值 $ $2$ 的蟾蜍。

注意，第一个咒语将黄金转化为硫磺，第二个咒语凭空创造黄金和硫磺，第三个咒语将黄金和硫磺转化为蟾蜍。

如果 Edythe 按顺序 1、2、3 施放这些咒语，她会先为第 1 个咒语从仓库取出价值 $ $7$ 的黄金。这样她就可以施放第 1 和第 2 个咒语，得到价值 $ $10$ 的黄金和 $ $15$ 的硫磺。对于最后一个咒语，她需要 $ $3$ 的黄金和 $ $20$ 的硫磺。她必须用掉迄今为止创造的所有硫磺、$ $3$ 的黄金，以及再从仓库取 $ $5$ 的硫磺。最终她会剩下价值 $ $9$ 的原材料（$ $7$ 的黄金和 $ $2$ 的蟾蜍）。

但还有更好的方案。如果她按顺序 3、1、2 施放咒语，最终她会剩下价值 $ $27$ 的原材料（$ $10$ 的黄金、$ $15$ 的硫磺和 $ $2$ 的蟾蜍）。

Input Format

输入的第一行给出测试用例数 $\mathbf{T}$。接下来有 $\mathbf{T}$ 组测试用例。每组测试用例的第一行包含 $\mathbf{N}$ 和 $\mathbf{M}$。$\mathbf{M}$ 是世界中原材料的种类数。接下来的 $\mathbf{N}$ 行，每行包含 $\mathbf{M}$ 个整数，描述一个咒语。每个整数表示对应原材料的价值（或成本）。负整数表示输入原材料的美元成本；正整数表示输出原材料的美元价值；零表示该咒语既不产生也不消耗该原材料。这也意味着没有任何咒语会同时消耗和产生同一种原材料。

Output Format

对于每个测试用例，输出一行，格式为 “Case #x: y”，其中 $\mathrm{x}$ 是测试用例编号（从 1 开始），$\mathrm{y}$ 是 Edythe 最终能拥有的最大原材料价值。

2
3 1
1
0
-1
3 3
-7 5 0
10 10 0
3 -20 2

Case #1: 1
Case #2: 27

Hint

数据范围

• $1 \leq \mathbf{T} \leq 100$。
• $1 \leq \mathbf{N} \leq 100$。
• 每个咒语中的每个整数 $-100 \leq \text{值} \leq 100$。

小数据集（8 分）

• 时间限制：240 5 秒。
• $1 \leq \mathbf{M} \leq 2$。

大数据集

• 时间限制：480 10 秒。
• $1 \leq \mathbf{M} \leq 8$。

由 ChatGPT 4.1 翻译