Mr. Sheep 沉迷于一款电脑游戏。在游戏中，他扮演一名超级英雄与邪恶势力战斗。装备在游戏中非常重要，而 Mr. Sheep 认为“补刀斧”（Quelling Blade）是最强大的武器。

在游戏中，每种类型的武器都需要花费英雄一定的金钱，并为英雄带来收益。如果英雄购买了两件武器（无论类型是否相同），收益值都会累加。也就是说，如果英雄购买了两件收益分别为 3 和 5 的武器，他将获得总计 $8=3+5$ 的收益值。

每种武器都有一些前置需求。如果英雄想要购买某种武器，他可能需要先拥有其他武器。例如，如果英雄想要购买一把“圣剑”（Divine Rapier），他需要先拥有“恶魔刀锋”（Demon Edge）和“圣者遗物”（Scared Relic）。当然，如果他想购买第二把“圣剑”，他必须先购买另一把“恶魔刀锋”和另一把“圣者遗物”。注意，交易后已有的武器不会消失。此外，一种武器可能需要多件同类型的武器。你可以假设一种类型的武器最多被另一种类型的武器所需要。

英雄忙于战斗，没有时间赚钱。幸运的是，游戏每秒会给英雄 1 枚金币。因此，如果英雄想要购买“补刀斧”，他达到目标所需的最短总时间是可以轻松计算出来的。

Mr. Sheep 是一个完美主义者。他不仅希望尽快获得“补刀斧”，还希望优化游戏过程中的每一秒。他将游戏的效用定义为英雄在每一秒获得的收益值之和。他计算的是从游戏开始到他获得“补刀斧”那一秒之前的总效用。你可以参考样例以获得进一步的理解。换句话说，你需要为英雄定义一套购买武器的流程，在获得“补刀斧”的总时间最短的前提下，使游戏的效用最大化。

输入格式

输入的第一行包含一个整数，表示测试用例的数量。注意，大多数测试用例规模较小。

对于每个测试用例，第一行包含一个整数 $N$，表示不同类型武器的数量（$1 \le N \le 1000$）。

接下来的行描述了这些武器。对于每种武器，第一行包含两个整数 $B$ 和 $C$，分别表示该类武器的收益值和成本（$1 \le B, C \le 2^{31}-1$）。接下来的一行包含一个整数 $P$，表示该武器的需求数量。接下来的 $P$ 行，每行包含两个整数 $I$ 和 $A$，表示该武器需要 $A$ 件索引为 $I$ 的武器。

武器的索引从 1 到 $N$。“补刀斧”是第一种类型的武器。你可以假设“补刀斧”所需的武器总数小于 $1,000,000$。同时注意，“补刀斧”可以在有限的游戏时间内买到，且一种类型的武器最多被另一种类型的武器所需要。

输出格式

对于每个测试用例，输出一个整数，表示最优效用。你可以假设答案在 64 位有符号整数范围内。

样例

输入格式 1

2
3
1 1
1
2 2
2 1
1
3 1
1 1
0
3
1 1
1
2 2
1 1
1
3 1
2 1
0

输出格式 1

Case #1: 14
Case #2: 17