Description

你是一个国家中最技艺高超的炼金术士，这个国家认为黄金、铂金和白银等金属毫无趣味，却极为珍视铅。在已知的 $\mathrm{M}$ 种金属中，铅在你的元素周期表上编号为 1。国家的领袖要求你利用国库中的金属，尽可能多地制造铅。

对于每种金属（包括铅），你都知道恰好有一种配方，可以通过消耗两种原料金属各一克来制造该金属一克。（如果你在思考质量守恒定律，另一克会变成无用的废弃物。）配方不能用部分克数操作。然而，只要你有足够的原料，每种配方你都可以使用任意多次（也可以不用）。

如果你做出最优选择，最终你最多能得到多少克铅？注意，操作结束后，可能还会剩下一些非铅金属。

Input Format

输入的第一行为测试用例数 $\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 号金属。

Output Format

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

3
3
2 3
1 3
1 2
5 2 3
5
3 4
3 4
4 5
3 5
1 3
0 8 6 2 4
4
3 4
2 3
2 3
2 3
0 1 1 0

Case #1: 7
Case #2: 4
Case #3: 0

Hint

样例解释

样例 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 翻译