你是你所在国家最顶尖的炼金术士。在这个国家，人们认为金、铂、银等金属毫无价值，但却非常看重铅。世界上已知有 $M$ 种金属；在你的元素周期表中，铅是 1 号金属。国家的领导人要求你利用国库中的金属尽可能多地制造铅。

对于每种金属（包括铅），你都确切地知道一种配方：通过消耗两种原料金属各 1 克，可以制造出 1 克该种金属。（如果你对质量守恒定律感到好奇，那么另一克金属在过程中作为无用的废料损失掉了。）这些配方不能处理不足 1 克的原料。但是，只要你每次都有所需的原料，你就可以根据需要多次使用每种配方（或者完全不用）。

如果你做出最优选择，你最终能得到的铅的总量是多少？注意，在你完成操作后，你可能会剩下一些除铅以外的其他金属。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $M$：世界上已知的金属数量。接下来有 $M$ 行，每行包含两个整数 $R_{i1}$ 和 $R_{i2}$；这 $M$ 行中的第 $i$ 行表示你可以通过消耗 1 克 $R_{i1}$ 金属和 1 克 $R_{i2}$ 金属来制造 1 克 $i$ 号金属。最后一行包含 $M$ 个整数 $G_1, G_2, \dots, G_M$；$G_i$ 是国库中 $i$ 号金属的克数。

铅是 1 号金属。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是你最终能得到的铅的最大克数。

数据范围

$1 \le T \le 100$。 $1 \le R_{i1} < R_{i2} \le M$，对于所有 $i$ 均成立。

测试集 1（可见） $2 \le M \le 8$。 $0 \le G_i \le 8$，对于所有 $i$ 均成立。

测试集 2（隐藏） $2 \le M \le 100$。 $0 \le G_i \le 100$，对于所有 $i$ 均成立。

测试集 3（隐藏） $2 \le M \le 100$。 $0 \le G_i \le 10^9$，对于所有 $i$ 均成立。

样例

样例输入 1

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

样例输出 1

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

说明

在样例 1 中，最优策略是使用 2 克 2 号金属和 2 克 3 号金属来额外制造 2 克铅，总共得到 7 克铅。

在样例 2 中，最优策略是先使用 2 克 3 号金属和 2 克 5 号金属制造 2 克 4 号金属，然后使用 4 克 3 号金属和 4 克 4 号金属制造 4 克铅。注意，两个配方可能具有相同的两种原料（你只是使用了不同的炼金技术）。还要注意，并非每种金属都一定是其他某种配方的原料；在本例中，2 号金属从不作为原料。

在样例 3 中，注意一种金属可能被用于制造它自身。（有时炼金术的定律可能很荒谬！）遗憾的是，在这种情况下无法制造出任何铅。注意，由于配方仅适用于 1 克单位的量，你不能例如使用 0.5 克 2 号金属和 0.5 克 3 号金属来制造 0.5 克 4 号金属，然后再使用 0.5 克 3 号金属和 0.5 克 4 号金属来制造 0.5 克铅。