很久很久以前，在遥远的地方有一个魔法大陆。

大陆上有 $N$ 种魔法水晶，每种水晶都蕴含着古老的魔力。在市场上，每种魔法水晶都有其对应的单价。作为最强大的魔法师，熊猫先生可以通过收集一定数量的其他水晶来合成某些类型的水晶。他也可以消耗一定数量的魔力来直接创造某些类型的水晶。

现在，熊猫先生希望通过消耗不超过 $M$ 点魔力来创造任意数量的水晶。他想知道通过出售他所创造和合成的所有水晶，他最多能赚取多少钱。

输入格式

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

每个测试用例的第一行包含 3 个正整数 $M, N$ 和 $K$，分别表示熊猫先生拥有的魔力值、魔法大陆上的水晶种类数以及水晶合成方程的数量。

接下来有 $N$ 行，每行以 0 或 1 开头，表示熊猫先生是否能直接创造该种水晶。

如果第 $i$ 行以 0 开头，表示熊猫先生无法直接创造第 $i$ 种水晶。该行随后有一个整数 $p_i$，表示第 $i$ 种水晶的单价。

如果第 $i$ 行以 1 开头，表示熊猫先生可以创造第 $i$ 种水晶。该行随后有两个正整数 $c_i$ 和 $p_i$，分别表示创造一个第 $i$ 种水晶所需的魔力消耗以及该种水晶的单价。

接下来的 $K$ 行，每行以两个整数 $x_i$ 和 $y_i$ 开头，表示合成一个第 $x_i$ 种水晶需要满足 $y_i$ 条规则。随后有 $y_i$ 对正整数 $u_j$ 和 $v_j$，表示合成一个第 $x_i$ 种水晶，需要收集 $v_j$ 个第 $u_j$ 种水晶。只有当所有关于 $u_j$ 和 $v_j$ 的规则都满足时，熊猫先生才能合成一个第 $x_i$ 种水晶。

输出格式

对于每个测试用例，输出一行 “Case #x: y”，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是熊猫先生能赚取的最大金额。

数据范围

• $1 \le T \le 100$
• $1 \le M \le 10000$
• $1 \le N \le 200$
• $1 \le K \le 200$
• $1 \le x_i, u_j \le N$
• 对于每个水晶合成方程，所有的 $u_j$ 均不相同
• $1 \le v_j \le 100$
• $1 \le c_i, p_i \le 10000$

样例

输入 1

2
100 3 2
0 20
1 15 10
1 2 1
1 2 2 1 3 1
2 1 3 2
100 3 2
1 3 1
1 4 1
0 10
3 1 1 3
3 1 2 2

输出 1

Case #1: 330
Case #2: 121