경주

n개의 체크포인트가 있다. 각 선수는 원점 (0, 0)에서 출발해 체크포인트를 일부 선택해 방문한 뒤 다시 원점으로 돌아온다. 방문하는 체크포인트의 번호는 반드시 증가하는 순서여야 한다. 체크포인트 번호가 1부터 n까지라면 1, 2, 5번을 이 순서로 방문할 수 있지만, 4번 다음에 2번을 방문할 수는 없다.

이동할 때는 두 지점을 잇는 직선 경로만 사용할 수 있다. 그 선분 위에 다른 체크포인트가 놓여 있으면, 그 체크포인트는 방문한 것으로 처리할 수도 있고 지나칠 수도 있다. 각 체크포인트의 점수는 한 번만 얻을 수 있다.

선수마다 달릴 수 있는 최대 거리 d가 주어진다. 제한 거리 안에서 원점으로 돌아오면서 얻을 수 있는 최대 점수를 구하라.

입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스는 다음 형식이며, 전체 입력의 끝에는 0 한 줄이 주어진다.

• 첫째 줄에 체크포인트의 개수 n이 주어진다 (1 <= n <= 30).
• 다음 n개 줄에는 각 체크포인트의 좌표 x, y와 점수 s가 차례로 주어진다 (-5000 <= x, y <= 5000, 10 <= s <= 200).
• 이어서 선수 정보가 여러 줄 주어진다. 각 줄에는 선수 이름과 최대 거리 d가 공백으로 구분되어 주어진다 (0 <= d <= 10000). 선수 이름은 60글자를 넘지 않고 공백을 포함하지 않는다.
• # 0 한 줄은 현재 테스트 케이스의 선수 목록이 끝났음을 뜻한다.

모든 거리는 평면에서의 직선거리로 계산한다.

각 테스트 케이스마다 먼저 Race r을 출력한다. r은 1부터 시작하는 테스트 케이스 번호이다.

그 다음에는 선수 정보를 입력받은 순서대로 한 줄에 하나씩 이름: 점수 형식으로 출력한다.