슈퍼캡 여행

2037년, 최초의 상업용 철도 기관차가 나온 지 225년 뒤에 초음속 자기부상 캡슐인 슈퍼캡이 운행을 시작했다. 슈퍼캡은 최고 $512$ m/s로 달리므로 도시 사이를 몇 초 만에 오간다.

슈퍼캡은 속도를 즉시 바꾸고, 유지하는 속도는 언제나 m/s 단위로 2의 거듭제곱이다. 한 번의 운행은 정확히 $D$미터를 달리고, 정지 상태에서 출발해 정지 상태로 끝나며, 네 구간으로 나뉜다.

1. 가속. 첫 1초는 $2^0 = 1$ m/s, 다음 1초는 $2^1 = 2$ m/s, 그다음 1초는 $2^2 = 4$ m/s처럼 매초 속도를 두 배로 올려 상한 속도 $U$에 도달한다. 거치는 속도는 $U$까지 포함해 각각 정확히 1초씩 유지한다.
2. 상한 활주. 상한 속도 $U$를 $g$초 더 유지한다. $g \ge 0$이다.
3. 감속. 매초 속도를 절반으로 줄여 $U/2$에서 하한 속도인 $16$ m/s까지 내려온다. 거치는 속도는 $16$ m/s까지 포함해 각각 정확히 1초씩 유지한다.
4. 종료 활주. $16$ m/s를 정수 초만큼 유지한 다음 $8$ m/s, $4$ m/s, $2$ m/s, $1$ m/s를 차례로 유지하고 멈춘다. 다섯 개의 초 수는 각각 0일 수 있어서 중간 속도를 건너뛸 수도 있다.

아래 속도-시간 그래프는 전형적인 운행 모습이다.

상한 속도는 마음대로 고를 수 없다. 슈퍼캡은 갈 수 있는 만큼 가속하므로, $U$는 가속 구간과 감속 구간만으로도 거리 안에 들어가는, 즉 $(2U - 1) + (U - 16) \le D$를 만족하는 $512$ 이하의 가장 큰 2의 거듭제곱이다.

운행 요금은 다음 값에 비례한다.

$A - 100B$

$A$는 $16$ m/s보다 빠르게 달린 시간(초)이고, $B$는 $16$ m/s 이하로 달린 시간(초)이다. 하한 속도보다 빠르게 달린 시간은 수익이 되고, 하한 속도 이하로 달린 1초는 그보다 빠르게 달린 1초가 벌어들이는 금액의 100배를 깎는다. 각 도시의 요금 점수는 정확히 $D$미터를 달리는 모든 운행 가운데 $A - 100B$의 최댓값이다.

1단계 건설에서는 어느 지역의 수도 $Z$가 인접한 지역마다 노선 하나씩을 얻고, 그 노선은 그 지역의 도시 한 곳에만 닿는다. 같은 지역 안의 도시끼리는 노선으로 잇지 않는다. 인접한 각 지역에서 요금 점수가 가장 큰 도시를 구하라.

첫 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 10$)가 주어진다.

각 테스트 케이스의 첫 줄에는 인접한 지역의 수 $R$ ($1 \le R \le 10$)이 주어지고, 이어서 $R$개 지역의 정보가 순서대로 주어진다.

각 지역의 정보는 그 지역에서 슈퍼캡 역이 있는 도시의 수 $C$ ($1 \le C \le 10$)로 시작한다. 다음 $C$개 줄에는 도시 이름 $Y$와 정수 $D$ ($1000 \le D \le 2 \times 10^6$)가 주어진다. $Y$는 영문 알파벳으로만 이루어진 한 단어이고, $D$는 수도 $Z$의 역에서 도시 $Y$의 역까지의 거리를 미터로 나타낸 값이다. 한 지역 안에서 거리는 모두 다르다.

각 테스트 케이스마다 한 줄을 출력한다. 줄은 Case #x:로 시작하고, $x$는 $1$부터 세는 테스트 케이스 번호이다. 그 뒤에 공백 하나를 두고 고른 도시 이름을 공백 하나로 구분해 출력한다. 도시 이름은 그 테스트 케이스의 지역 순서와 같은 순서로 놓는다. 한 지역에서 요금 점수가 가장 큰 도시가 여럿이면 입력에 먼저 나온 도시를 고른다.