你正在玩一个带有精美卡牌的游戏。每张卡牌都有三个奖励数字：卡牌奖励 $c$、分数奖励 $s$ 和回合奖励 $t$。部分卡牌初始在你的手中，其余的在桌上的牌堆里。你初始拥有一个回合。

在每一回合中，你可以选择手中的任意一张卡牌并打出。如果该卡牌的奖励数字为 $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"，其中 $S$ 是你在回合耗尽前能获得的最大分数。

数据范围

$1 \le T \le 100$。 $1 \le N$。 $0 \le M$。 $N + M \le 80$。

小数据集（测试集 1 - 可见；15 分）

$0 \le c \le 1$。 $0 \le s \le 20$。 $0 \le t \le 20$。

大数据集（测试集 2 - 隐藏；35 分）

$0 \le c \le 2$。 $0 \le s \le 50$。 $0 \le t \le 50$。

样例

样例输入 1

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

样例输出 1

Case #1: 6
Case #2: 8