Description

你正在玩一款使用特殊卡牌的游戏。每张卡牌都有三个奖励数值：卡牌奖励 $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   |   -  |
+---------+------------+-------+------+

可以看到，卡牌奖励和回合奖励可以让你连续打出多张卡牌，直到无法继续为止。

Input Format

第一行输入一个整数 $T$，表示测试用例的数量。接下来有 $T$ 组测试用例。

每组测试用例的第一行包含一个整数 $N$，表示你手中的卡牌数量。接下来的 $N$ 行，每行包含三个整数 $c$、$s$、$t$，分别表示一张手牌的奖励数值。

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

Output Format

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

2
4
1 0 0
1 1 1
0 5 0
1 2 0
0
2
1 1 1
0 6 0
1
0 1 3

Case #1: 6
Case #2: 8

Hint

数据范围

• $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 翻译