题目描述

There are many great athletes in the world, and it's very hard to say who is the best in the world at a particular sport, especially when different athletes have won different competitions. Here's one possible system for ranking athletes:

1. Determine the number P of finishing places in any competition that will be worth points for athletes, and how many points $S_i$ each of those finishing places is worth. For example, for $P = 3$, one possible assignment would be 1000 points for 1st place, 500 for 2nd place, and 300 for 3rd place, and 0 for anything below that. (We assume there are no ties within competitions.)

2. Since not all competitions are equally important, assign a weight $W_i$ to each one. The score gained by an athlete for a competition will be the points from step 1, modified by the weight for that competition. For example, we may decide that Olympics has a weight of 5, and, continuing with our example from above, the winner of the Olympics would receive $5 \times 1000 = 5000$ points.

3. Since we don't want to reward athletes simply for participating in many competitions, we count only the M highest scores received by an athlete across all competitions. For example, if M = 2 and an athlete earns scores of $1000\times 5$, $500\times 1$, and $300\times 3$ in three different competitions, only the 5000 and 900 would be counted.

You are given the points per finishing place, the weights of the competitions, and the results of the competitions. Can you rank all of the athletes who appeared in the competitions? If multiple athletes have the same score, they will share the same rank and listed in alphabetical order of their names.

输入格式

The first line of the input gives the number of test cases, $T$. $T$ test cases follow; each test case consists of the following:

1. One line with an integer $P$, the number of top places for which points are awarded.
2. One line consists with $P$ integers representing the scores $S_i$ for the top places, starting with first place and continuing down the places.
3. One line with an integer $N$, the number of competitions.
4. $N$ lines, each of which represents a competition. Each line begins with $W_i$, the weight of this competition, and continues with the $P$ names of the athletes who finished in the top $P$ places. They are listed in descending order starting from first place.
5. One line with an integer $M$, the maximum number of competitions counted toward an athlete's score.

输出格式

For each test case, output one line containing "Case #x:", where x is the test case number (starting from $1$). Then output one line for each athlete, from highest rank to lowest rank, with the format $r$ : name, where $r$ is the rank of the athlete and name is the name of the athlete. You need to rank all of the athletes that appeared in the input.

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

提示

In the first case, Bolt scored a total of $7000$ in his two competitions. Gay would have scored a total of $8500$ if all competitions were counted, but since only the top $2$ competitions are counted in this case, Gay scored $6500$ and ranked second. Since Peimeng and Tianbing both scored $1500$, they both ranked 3rd and listed by their names. Larry is last, since he scored only $1000$.

Limits

$1 \le T \le 10$.

$1 \le S_i \le 1000$.

$S_i > S_{i+1}$.

$1 \le W_i \le 1000$.

Each name consists only of characters A through Z, and is at most $10$ characters long.

Small dataset (Test Set 1 - Visible)

$1 \le P \le 10$.

$1 \le N \le 10$.

$1 \le M \le 10$.

Large dataset (Test Set 2 - Hidden)

$1 \le P \le 100$.

$1 \le N \le 100$.

$1 \le M \le 100$.