gRanks

세계에는 훌륭한 선수들이 많으며, 특히 서로 다른 선수들이 서로 다른 대회에서 우승했을 때 특정 종목에서 누가 세계 최고인지 말하기는 매우 어렵다. 다음은 선수들의 순위를 정할 수 있는 한 가지 체계이다.

1. 임의의 대회에서 선수들에게 점수를 부여할 입상 순위의 수 P와, 각 입상 순위에 부여할 점수 $S_{i}$를 정한다. 예를 들어 P = 3일 때, 가능한 배점 방식 중 하나는 1st 순위에 1000점, 2nd 순위에 500점, 3rd 순위에 300점, 그보다 낮은 순위에는 0점을 부여하는 것이다. (대회 내에서는 공동 순위가 없다고 가정한다.)

2. 모든 대회가 똑같이 중요하지는 않으므로, 각 대회에 가중치 $W_{i}$를 부여한다. 선수가 한 대회에서 얻는 점수는 1단계의 점수를 해당 대회의 가중치로 조정한 값이다. 예를 들어 올림픽의 가중치를 5로 정할 수 있으며, 위의 예를 이어 가면 올림픽 우승자는 5 * 1000 = 5000점을 받는다.

3. 단순히 많은 대회에 참가한 선수에게 보상하고 싶지는 않으므로, 한 선수가 모든 대회에서 받은 점수 중 가장 높은 M개만 합산한다. 예를 들어 M = 2이고 한 선수가 서로 다른 세 대회에서 10005, 5001, 300*3의 점수를 얻었다면, 5000와 900만 합산된다.

입상 순위별 점수, 대회의 가중치, 대회 결과가 주어진다. 대회에 등장한 모든 선수의 순위를 정할 수 있는가? 여러 선수의 점수가 같다면 같은 순위를 공유하며, 이름의 알파벳순으로 나열한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1 GB. 1 ≤ T ≤ 10. 1 ≤ $S_{i}$ ≤ 1000. $S_{i}$ > $S_{i+1}$. 1 ≤ $W_{i}$ ≤ 1000. 각 이름은 A부터 Z까지의 문자로만 구성되며, 길이는 최대 10자이다.

작은 데이터 세트 (Test Set 1 - 공개)

1 ≤ P ≤ 10. 1 ≤ N ≤ 10. 1 ≤ M ≤ 10.

큰 데이터 세트 (Test Set 2 - 비공개)

1 ≤ P ≤ 100. 1 ≤ N ≤ 100. 1 ≤ M ≤ 100.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 다음과 같이 구성된다.

1. 점수가 부여되는 상위 순위의 수를 나타내는 정수 P가 한 줄에 주어진다.
2. 선두부터 낮은 순위로 이어지는 상위 순위의 점수 $S_{i}$를 나타내는 P개의 정수가 한 줄에 주어진다.
3. 대회의 수를 나타내는 정수 N이 한 줄에 주어진다. 4. 이어지는 N개의 줄은 각각 하나의 대회를 나타낸다. 각 줄은 이 대회의 가중치인 $W_{i}$로 시작하고, 상위 P개 순위에 든 선수 P명의 이름이 이어진다. 선수들은 선두부터 내림차순으로 나열된다.
4. 선수의 점수에 합산되는 대회의 최대 개수를 나타내는 정수 M이 한 줄에 주어진다.

각 테스트 케이스마다 "Case #x:"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며 1부터 시작한다. 그런 다음 순위가 가장 높은 선수부터 가장 낮은 선수까지 각 선수에 대해 r: name 형식으로 한 줄씩 출력한다. 여기서 r는 선수의 순위이고 name는 선수의 이름이다. 입력에 등장한 모든 선수의 순위를 정해야 한다.

첫 번째 케이스에서 Bolt는 두 대회에서 총 7000점을 얻었다. 모든 대회를 합산했다면 Gay는 총 8500점을 얻었겠지만, 이 케이스에서는 상위 2개 대회만 합산하므로 Gay는 6500점을 얻어 두 번째 순위가 되었다. Since Peimeng와 Tianbing은 둘 다 1500점을 얻었으므로, 둘 다 3rd 순위가 되었으며 이름순으로 나열된다. Larry는 1000점만 얻었으므로 마지막이다.