P13237 [GCJ 2015 Finals] Merlin QA

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$ 的蟾蜍）。

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

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

**数据范围** - $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 翻译