gRanks

The world has many great athletes. When different athletes win different competitions, it is hard to say who is the best. Here is one way to rank them.

1. Fix the number $P$ of finishing places that are worth points, and the number of points $S_i$ awarded for place $i$. For example, with $P = 3$ you could award 1000 points for first place, 500 for second place, 300 for third place, and 0 for anything below that. There are no ties within a competition.
2. Competitions are not equally important, so competition $i$ gets a weight $W_i$. The score an athlete gains in that competition is the points from step 1 multiplied by the weight of the competition. For example, if the Olympics has weight 5, then in the example above the winner of the Olympics gains $5 \times 1000 = 5000$ points.
3. So that an athlete does not gain simply by entering many competitions, only the $M$ highest scores an athlete earned across all competitions are added up. For example, if $M = 2$ and an athlete earned $1000 \times 5$, $500 \times 1$ and $300 \times 3$ points in three competitions, only 5000 and 900 are added, for a total of 5900.

You are given the points per place, the weight of each competition, and the results of the competitions. Rank every athlete who appears in the competitions.

The first line contains the number of test cases $T$. Then $T$ test cases follow. Each test case consists of the following.

1. One line with the number $P$ of top places that are worth points.
2. One line with the $P$ scores $S_1, S_2, \dots, S_P$, starting with first place and going down.
3. One line with the number $N$ of competitions.
4. $N$ lines, each holding the result of one competition. A line begins with the weight $W_i$ of that competition and continues with the names of the athletes who finished in the top $P$ places, listed from first place downward.
5. One line with the maximum number $M$ of competitions counted toward an athlete's score.

For each test case, first print Case #x:, where $x$ is the test case number starting from 1. Then print every athlete who appears in the input, from the highest rank to the lowest, one per line in the format r: name, where $r$ is the rank of the athlete and name is the name.

Athletes with the same total share the same rank. The rank of an athlete is one plus the number of athletes with a strictly higher total. Athletes with the same rank are printed in alphabetical order of their names.

• $1 \le T \le 10$
• $1 \le P \le 100$
• $1 \le N \le 100$
• $1 \le M \le 100$
• $1 \le S_i \le 1000$
• $S_i > S_{i+1}$
• $1 \le W_i \le 1000$
• Each name uses only the uppercase letters A through Z and is at most 10 characters long.
• No name appears twice in the result of one competition.

In the first example BOLT earned 7000 points in total from two competitions. GAY would have 8500 points if all four competitions counted, but only the top 2 count, so GAY has 6500 points and second place. PEIMENG and TIANBING both have 1500 points, so they share rank 3 and are printed in alphabetical order. LARRY has only 1000 points and comes last.