gRanks (Small)

문제

세계에는 뛰어난 선수가 많다. 서로 다른 선수가 서로 다른 대회에서 우승하면 누가 가장 강한지 가리기 어렵다. 다음은 선수의 순위를 매기는 한 가지 방법이다.

대회에서 점수를 받는 상위 등수의 개수 $P$ 와, $i$ 등에게 주어지는 점수 $S_i$ 를 정한다. 예를 들어 $P = 3$ 이면 1등 1000점, 2등 500점, 3등 300점으로 정하고 그 아래 등수는 0점으로 둔다. 한 대회 안에 공동 등수는 없다.
대회마다 중요도가 다르므로 각 대회에 가중치 $W_i$ 를 매긴다. 선수가 한 대회에서 얻는 점수는 1번에서 정한 등수 점수에 그 대회의 가중치를 곱한 값이다. 올림픽의 가중치가 5라면 위의 예에서 올림픽 우승자는 $5 \times 1000 = 5000$ 점을 얻는다.
대회에 많이 나갔다는 이유만으로 유리해지지 않도록, 각 선수가 얻은 점수 중 큰 것부터 $M$ 개만 더해 합계 점수로 삼는다. $M = 2$ 이고 어떤 선수가 세 대회에서 $1000 \times 5$ , $500 \times 1$ , $300 \times 3$ 점을 얻었다면 5000과 900만 더한다.

등수별 점수, 각 대회의 가중치, 대회 결과가 주어진다. 입력에 등장하는 모든 선수의 순위를 매겨라.

입력

첫 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 이어서 $T$ 개의 테스트 케이스가 주어지며, 각 테스트 케이스는 다음과 같이 이루어진다.

첫 줄에 점수를 받는 상위 등수의 개수 $P$ .
둘째 줄에 1등부터 $P$ 등까지의 점수 $S_1, S_2, \dots, S_P$ 가 등수 순서대로 $P$ 개.
셋째 줄에 대회의 수 $N$ .
다음 $N$ 개 줄에 각 대회의 결과가 한 줄에 하나씩. 각 줄은 그 대회의 가중치 $W_i$ 로 시작하고, 이어서 상위 $P$ 등에 든 선수의 이름이 1등부터 차례대로 $P$ 개 주어진다.
마지막 줄에 한 선수의 합계에 반영되는 대회 수의 최댓값 $M$ .

출력

각 테스트 케이스마다 먼저 Case #x:를 한 줄에 출력한다. $x$ 는 1부터 시작하는 테스트 케이스 번호다. 그다음 입력에 등장한 모든 선수를 한 줄에 한 명씩 r: name 형식으로 출력한다. $r$ 은 그 선수의 순위, $name$ 은 이름이다.

선수의 순위는 자신보다 합계 점수가 높은 선수의 수에 1을 더한 값이다. 따라서 합계 점수가 같은 선수는 같은 순위를 받고, 그다음 순위는 같은 순위를 받은 인원수만큼 건너뛴다. 순위가 높은 선수부터 출력하고, 순위가 같으면 이름의 사전순으로 출력한다. 테스트 케이스 사이에 빈 줄을 넣지 않는다.

제한

$1 \le T \le 10$
$1 \le P \le 10$
$1 \le S_i \le 1000$
$S_i > S_{i+1}$
$1 \le N \le 10$
$1 \le W_i \le 1000$
$1 \le M \le 10$
선수 이름은 A부터 Z까지의 문자로만 이루어지고, 길이는 10 이하다.

힌트

첫 번째 예제에서 BOLT는 두 대회에서 합계 7000점을 얻어 1위다. GAY는 네 대회의 점수를 모두 더하면 8500점이지만 상위 두 개만 세므로 6500점이 되어 2위다. PEIMENG과 TIANBING은 둘 다 1500점이라 공동 3위이고, 이름의 사전순으로 나열한다. 공동 3위가 두 명이므로 그다음 순위는 4위가 아니라 5위이고, 1000점을 얻은 LARRY가 5위다.