P13141 [GCJ 2018 #1B] Transmutation

你是一个国家中最技艺高超的炼金术士，这个国家认为黄金、铂金和白银等金属毫无趣味，却极为珍视铅。在已知的 $\mathrm{M}$ 种金属中，铅在你的元素周期表上编号为 1。国家的领袖要求你利用国库中的金属，尽可能多地制造铅。 对于每种金属（包括铅），你都知道恰好有一种配方，可以通过消耗两种原料金属各一克来制造该金属一克。（如果你在思考质量守恒定律，另一克会变成无用的废弃物。）配方不能用部分克数操作。然而，只要你有足够的原料，每种配方你都可以使用任意多次（也可以不用）。 如果你做出最优选择，最终你最多能得到多少克铅？注意，操作结束后，可能还会剩下一些非铅金属。

输入的第一行为测试用例数 $\mathbf{T}$。接下来有 $\mathbf{T}$ 组测试用例。每组测试用例的第一行为一个整数 $\mathrm{M}$，表示已知的金属种类数。接下来有 $\mathrm{M}$ 行，每行包含两个整数 $\mathbf{R}_{\mathbf{i} 1}$ 和 $\mathbf{R}_{\mathbf{i} 2}$，表示可以通过消耗 $\mathbf{R}_{\mathbf{i} 1}$ 号金属一克和 $\mathbf{R}_{\mathbf{i} 2}$ 号金属一克，制造出 $\mathrm{i}$ 号金属一克。最后一行包含 $\mathrm{M}$ 个整数 $\mathbf{G}_{1}, \mathbf{G}_{2}, \ldots, \mathbf{G}_{\mathbf{M}}$，其中 $\mathbf{G}_{\mathbf{i}}$ 表示国库中 $\mathrm{i}$ 号金属的克数。铅为 1 号金属。

对于每组测试用例，输出一行，格式为 `Case #x: y`，其中 $\mathrm{x}$ 为测试用例编号（从 1 开始），$\mathrm{y}$ 为你最终能获得的最大铅的克数。

**样例解释** 样例 1 中，最优策略是用 2 克 2 号金属和 2 克 3 号金属制造 2 克铅，最终共得到 7 克铅。 样例 2 中，最优策略是先用 2 克 3 号金属和 2 克 5 号金属制造 2 克 4 号金属，然后用 4 克 3 号金属和 4 克 4 号金属制造 4 克铅。注意，可能有两种配方使用相同的两种原料金属（只是炼金术手法不同）。也要注意，并不是每种金属都一定会作为其他配方的原料；在本例中，2 号金属从未作为原料。 样例 3 中，注意某种金属可能可以用来制造自身。（有时候炼金术的规律也很奇怪！）但在本例中无法制造出任何铅。注意，由于配方只能以整数克操作，不能用 0.5 克 2 号金属和 0.5 克 3 号金属制造 0.5 克 4 号金属，再用 0.5 克 3 号金属和 0.5 克 4 号金属制造 0.5 克铅。 **数据范围** - $1 \leq T \leq 100$。 - 对所有 $i$，$1 \leq \mathbf{R_{i1}} < \mathbf{R_{i2}} \leq M$。 **测试点 1（15 分，可见）** - $2 \leq M \leq 8$。 - 对所有 $i$，$0 \leq \mathbf{G_i} \leq 8$。 **测试点 2（18 分，隐藏）** - $2 \leq M \leq 100$。 - 对所有 $i$，$0 \leq \mathbf{G_i} \leq 100$。 **测试点 3（12 分，隐藏）** - $2 \leq M \leq 100$。 - 对所有 $i$，$0 \leq \mathbf{G_i} \leq 10^9$。 由 ChatGPT 4.1 翻译