SP9694 QB - Quelling Blade

Mr. Sheep 沉迷于一款电脑游戏。在游戏中，他扮演一位超级英雄，与邪恶势力展开斗争。装备在这款游戏中非常重要，而 Mr. Sheep 认为「Quelling Blade」是最具威力的武器。 在游戏中，每种武器都需要花费一定的金币，并能为英雄带来相应的收益。如果英雄购买两件武器（无论种类是否相同），其收益值会叠加。也就是说，如果英雄购买了两把收益值分别为 3 和 5 的武器，总收益为 3 + 5 = 8。 每种武器都有其特定的购买需求。如果英雄想要购买某种武器，可能需要先获得其他一些特定武器。例如，若想获得「Divine Rapier」，必须先拥有「Demon Edge」和「Sacred Relic」。当然，若想再购买第二把「Divine Rapier」，则须额外拥有另一把「Demon Edge」和「Sacred Relic」。值得注意的是，交易后原有的武器不会消失。同时，某种类型的武器也可能需要多把同类型武器。可以假定每种武器最多只有一个需求者。 英雄忙于战斗，无法去赚取金币。不过，幸运的是，游戏每秒都会自动给他 1 枚金币。因此，如果 Mr. Sheep 想要购买「Quelling Blade」，可很容易计算出所需的最短时间。 Mr. Sheep 是个完美主义者。他不仅希望尽快获得「Quelling Blade」，还希望在每秒钟都能最大化收益。他定义游戏效用为从游戏开始到最终获得「Quelling Blade」之前每秒获得的总收益值。你需要为他设计一种购买策略，以便在最短时间内获得「Quelling Blade」并且最大化效用。

输入由多个测试用例组成，第一行给出测试用例的数量。大多数测试用例的规模相对较小。 对于每个测试用例，第一行包含一个整数 $N$，表示不同类型的武器数量。（$1 \le N \le 1000$） 接下来描述每种武器。每种武器的描述第一行包含两个整数 $B$ 和 $C$，分别表示该武器的收益值和花费。（$1 \le B, C \le 2^{31} - 1$）接下来的行中，第一行包含一个整数 $P$，表示该武器需满足的前置需求数量。接下来的 $P$ 行中，每行有两个整数 $I$ 和 $A$，表示该武器需要 $A$ 件编号为 $I$ 的武器。武器编号从 1 到 $N$。「Quelling Blade」为第 1 种武器。 可以肯定的是，「Quelling Blade」所需的全部武器数量不超过 1000000。此外，「Quelling Blade」可以在有限的游戏时间内获得，并且一种武器最多只被另一种武器所需。

对于每个测试用例，输出一个整数，表示最优效用。答案可以使用 64 位有符号整数表示。 **本翻译由 AI 自动生成**