P13367 [GCJ 2011 #1A] Pseudominion

你正在玩一款使用特殊卡牌的游戏。每张卡牌都有三个奖励数值：卡牌奖励 $c$，得分奖励 $s$，回合奖励 $t$。有些卡牌一开始就在你手中，其余的卡牌则在桌上的牌堆中。你从 $1$ 个回合开始。 在每个回合中，你可以从手牌中选择任意一张卡牌并打出。如果这张卡牌的奖励数值为 $c$，$s$，$t$，则会发生以下事件： - 这张卡牌会从你的手牌中移除，且之后不能再使用。 - 你从牌堆顶依次抽取 $c$ 张卡牌加入手牌。如果牌堆中剩余的卡牌数少于 $c$，则全部抽取。 - 你的总得分增加 $s$。 - 你的剩余回合数增加 $t$。 如果在某个回合开始时你手中没有任何卡牌，则该回合不会发生任何事情。你的目标是在回合数耗尽之前获得尽可能高的分数。 例如，假设你的手牌和牌堆包含如下卡牌： ``` +---+---+---+ +---+---+---+ HAND: | c | s | t | DECK: | c | s | t | +---+---+---+ +---+---+---+ Card #1: | 0 | 0 | 2 | Card #4: | 1 | 1 | 0 | Card #2: | 0 | 5 | 0 | Card #5: | 0 | 1 | 1 | Card #3: | 2 | 1 | 1 | Card #6: | 2 | 2 | 0 | +---+---+---+ +---+---+---+ ``` 下表展示了你如何通过这些卡牌获得 $8$ 分的得分。前三列分别表示你打牌前的手牌、剩余回合数和得分，最后一列表示你选择打出的卡牌编号。 ``` +---------+------------+-------+------+ | Hand | Turns left | Score | Play | +---------+------------+-------+------+ | 1, 2, 3 | 1 | 0 | 1 | | 2, 3 | 2 | 0 | 3 | | 2, 4, 5 | 2 | 1 | 2 | | 4, 5 | 1 | 6 | 5 | | 4 | 1 | 7 | 4 | | 6 | 0 | 8 | - | +---------+------------+-------+------+ ``` 可以看到，卡牌奖励和回合奖励可以让你连续打出多张卡牌，直到无法继续为止。

第一行输入一个整数 $T$，表示测试用例的数量。接下来有 $T$ 组测试用例。 每组测试用例的第一行包含一个整数 $N$，表示你手中的卡牌数量。接下来的 $N$ 行，每行包含三个整数 $c$、$s$、$t$，分别表示一张手牌的奖励数值。 然后输入一行，包含一个整数 $M$，表示牌堆中的卡牌数量。接下来的 $M$ 行，每行包含三个整数 $c$、$s$、$t$，分别表示一张牌堆卡牌的奖励数值。这些卡牌的顺序即为你抽取它们的顺序。

对于每个测试用例，输出一行，格式为 “Case #x: $S$”，其中 $x$ 表示测试用例编号（从 $1$ 开始），$S$ 表示在回合数耗尽前你能获得的最大得分。

**数据范围** - $1 \leq T \leq 100$。 - $1 \leq N$。 - $0 \leq M$。 - $N + M \leq 80$。 **小数据（15 分，测试点 1 - 可见）** - $0 \leq c \leq 1$。 - $0 \leq s \leq 20$。 - $0 \leq t \leq 20$。 - 时间限制：~~30~~ 6 秒。 **大数据（35 分，测试点 2 - 隐藏）** - $0 \leq c \leq 2$。 - $0 \leq s \leq 50$。 - $0 \leq t \leq 50$。 - 时间限制：~~60~~ 12 秒。 由 ChatGPT 4.1 翻译