题目描述

世界上有许多伟大的运动员，很难说在某一特定运动中谁是全世界最优秀的，尤其是当不同的运动员赢下了不同的比赛时。以下是一种可能的运动员排名系统：

1. 确定在任何比赛中，值得为运动员计算积分的完赛名次数量 $P$，以及每个名次所值的分数 $S_i$。例如，对于 $P = 3$，一种可能的分配方式是：第 1 名获得 1000 分，第 2 名获得 500 分，第 3 名获得 300 分，低于此名次得 0 分。（我们假设比赛内不存在并列情况。）

2. 由于并非所有比赛都同等重要，需要为每场比赛分配一个权重 $W_i$。运动员在某场比赛中获得的分数将是步骤 1 中的积分，再乘以该场比赛的权重。例如，我们可以规定奥运会的权重为 5，并结合前述例子，奥运会冠军将获得 $5 \times 1000 = 5000$ 分。

3. 由于不想仅仅因为运动员参加了很多比赛就给予奖励，我们只计算一位运动员在所有比赛中获得的分数中，最高的 $M$ 个分数。例如，如果 $M = 2$，而一位运动员在三场不同的比赛中分别获得了 $1000\times 5$、$500\times 1$ 和 $300\times 3$ 的分数，则只有 5000 分和 900 分会被计入。

给定每名次的得分、各比赛的权重以及比赛结果，你能为所有出现在比赛中的运动员排名吗？如果多名运动员得分相同，他们将共享相同的排名，并按他们名字的字母顺序列出。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来是 $T$ 个测试用例；每个测试用例包含以下内容：

1. 一行包含一个整数 $P$，表示授予积分的前 $P$ 个名次的数量。
2. 一行包含 $P$ 个整数，表示从前几名开始依次往下的名次得分 $S_i$。
3. 一行包含一个整数 $N$，表示比赛的数量。
4. 接下来 $N$ 行，每行代表一场比赛。每行以一个整数 $W_i$ 开始，表示该场比赛的权重，随后是获得前 $P$ 名的运动员的姓名。姓名按从第 1 名开始的降序列出。
5. 一行包含一个整数 $M$，表示计入一位运动员得分的最大比赛数量。

输出格式

对于每个测试用例，输出一行形如 "Case #x:" 的内容，其中 $x$ 是测试用例编号（从 $1$ 开始）。然后按从最高排名到最低排名的顺序，为每位运动员输出一行，格式为 $r$ : name，其中 $r$ 是该运动员的排名，name 是该运动员的姓名。你需要为输入中出现的所有运动员排名。

1
2
1000 500
6
5 BOLT GAY
4 GAY BOLT
1 GAY TIANBING
1 GAY PEIMENG
1 TIANBING LARRY
1 PEIMENG LARRY
2

Case #1:
1: BOLT
2: GAY
3: PEIMENG
3: TIANBING
5: LARRY

提示

在第一个样例中，Bolt 在他参加的两场比赛中总共获得了 $7000$ 分。Gay 如果所有比赛都计入的话，总共能获得 $8500$ 分，但此样例中只计入最高的 $2$ 场比赛，因此 Gay 获得了 $6500$ 分，排名第二。由于 Peimeng 和 Tianbing 都获得了 $1500$ 分，他们并列第三，并按姓名列出。Larry 排在最后，因为他只获得了 $1000$ 分。

限制

$1 \le T \le 10$。

$1 \le S_i \le 1000$。

$S_i > S_{i+1}$。

$1 \le W_i \le 1000$。

每个姓名仅由大写字母 A 到 Z 组成，且长度不超过 $10$ 个字符。

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

$1 \le P \le 10$。

$1 \le N \le 10$。

$1 \le M \le 10$。

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

$1 \le P \le 100$。

$1 \le N \le 100$。

$1 \le M \le 100$。

翻译由 DeepSeek V4 Pro 完成