Quelling Blade

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

每种武器都有对应的价格和收益值。英雄购买武器需要支付相应数量的金币，购买后即可获得该武器带来的收益。多件武器的收益值可以累加，例如，购买收益值分别为 $3$ 和 $5$ 的两件武器后，英雄的总收益值为 $8=3+5$。

购买某种武器前，英雄可能需要拥有若干件其他武器。例如，购买一件 Divine Rapier 可能需要先拥有一件 Demon Edge 和一件 Sacred Relic。如果还要购买第 $2$ 件 Divine Rapier，就必须再购买一件 Demon Edge 和一件 Sacred Relic。购买新武器时，作为前置条件的已有武器不会消失。一种武器可能需要多件相同种类的武器作为前置条件。

英雄忙于战斗，没有时间通过其他方式赚取金币。幸运的是，游戏每秒会给予英雄 $1$ 枚金币。因此，可以计算出他获得 Quelling Blade 所需的最短时间。

Sheep 先生是一位完美主义者。他不仅希望尽快获得 Quelling Blade，还希望使游戏的效用最大。游戏的效用定义为：从游戏开始，直到获得 Quelling Blade 的那一秒之前，英雄在每一秒所拥有的总收益值之和。

请在所有能够以最短总时间获得 Quelling Blade 的购买方案中，求出最大的游戏效用。

输入格式

第一行包含一个整数，表示测试用例的数量。测试用例数量较多，但其中大部分规模较小。

对于每组测试数据：

第一行包含一个整数 $N$，表示不同武器种类的数量。

接下来依次描述这 $N$ 种武器。对于每种武器：

• 第一行包含两个整数 $B$ 和 $C$，分别表示该种武器的收益值和价格；
• 第二行包含一个整数 $P$，表示购买该种武器所需的前置武器种类数；
• 接下来 $P$ 行，每行包含两个整数 $I$ 和 $A$，表示购买一件当前武器前，需要拥有 $A$ 件编号为 $I$ 的武器。

武器编号从 $1$ 到 $N$，其中编号为 $1$ 的武器是 Quelling Blade。

输出格式

对于每组测试数据，输出一行，格式为 Case #x: y。其中 $x$ 是从 $1$ 开始的测试用例编号，$y$ 是在最短时间内获得 Quelling Blade 时能够取得的最大游戏效用。

样例输入

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

样例输出

Case #1: 14
Case #2: 17

数据范围

• $1\le N\le 1000$；
• $1\le B,C\le 2^{31}-1$；
• Quelling Blade 所需的武器总数严格小于 $10^6$；
• 每种武器至多被另一种武器作为前置条件；
• 保证 Quelling Blade 可以在有限时间内获得；
• 保证答案可以用有符号 $64$ 位整数表示。

来源与许可

本题题面与测试数据整理自 BZOJ。

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

输出

Case #1: 14
Case #2: 17