시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1 1 1 100.000%

문제

n개의 체크포인트가 있고, 원점에서 출발하여 체크포인트들을 순서대로 방문하고 원점으로 돌아오는 경주가 진행된다. 이때 모든 체크포인트를 방문할 필요는 없지만 반드시 주어진 순서를 지키면서 방문해야 한다. 체크포인트 번호가 순서대로 1~n이라 할 때, 1, 2, 5번 순서대로 방문할 수는 있지만 4, 2번 순서대로는 방문할 수 없다.

원점이나 체크포인트 사이를 이동할 때는 반드시 직선 경로로 이동하는데, 이때 경로 위에 다른 체크포인트가 존재할 수도 있다. 이때는 방문해도 되고 방문하지 않아도 된다. 그리고 각각의 체크포인트에는 방문할 시 얻는 점수가 있는데, 우승자는 방문한 체크포인트의 점수 합이 가장 높은 사람이 된다. 물론 하나의 체크포인트에서는 점수를 한 번만 획득할 수 있다.

그러나 경주에 참여한 사람들이 모두 남규와 그 친구들이라 하나같이 약골이다. 그들은 각각 달릴 수 있는 거리 한계가 명확해서 그 안에 돌아오지 못하면 대회를 완주할 수 없다. 그들은 약골인데다 근성도 없어서 절대 그 거리보다 많이 뛸 수 없다. 다행히 각자는 자신이 얼마나 달릴 수 있는지 알고 있기 때문에, 한도 안에서 완주하면서 얻을 수 있는 점수가 최대 몇 점인지를 미리 계산해보려고 한다. 남규와 친구들을 위해 이를 구해 주는 프로그램을 작성해보자!

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 다음과 같이 이루어져 있으며, 전체 입력의 끝에는 0 하나가 주어진다.

  • 첫째 줄에 체크포인트의 개수 n이 주어진다(1 ≤ n ≤ 30).
  • 이어서 n개의 줄에 각 체크포인트의 좌표 x, y, 점수 s를 의미하는 정수 3개가 순서대로 주어진다(−5000 ≤ x, y ≤ 5000, 10 ≤ s ≤ 200).
  • 이어서 여러 줄에 각 선수의 이름과 최대한 달릴 수 있는 거리의 한계를 의미하는 정수 d가 공백으로 구분되어 줄마다 주어진다(0 ≤ d ≤ 10000). 선수의 이름은 60글자를 넘지 않으며 공백을 포함하지 않는다. 마지막 줄에는 선수 이름 대신 '# 0'이 주어지며, 이 줄은 각 테스트 케이스의 끝을 의미한다.

각 선수들은 원점(0, 0)에서 출발하여 몇몇 체크포인트를 방문했다가 다시 원점으로 돌아와야 한다. 아무것도 방문하지 않을 수도 있다. 경주가 이루어지는 공간은 완전히 평평한 2차원 공간이라고 가정한다.

출력

각 테스트 케이스마다 첫째 줄에 ‘Race r’을 출력한다. r에는 테스트 케이스의 번호가 들어간다. 이어서 각 줄마다 선수 정보를 입력받은 순서대로 선수의 이름과 얻을 수 있는 최대 점수를 출력 양식 ‘이름: 점수’에 맞게 출력한다.

예제 입력

5
750 -800 30
1500 0 50
750 750 60
-1250 750 70
-1000 -500 50
Chris 7000
Karl 6500
Tania 5000
# 0
4
500 0 10
0 500 10
-500 0 10
0 -500 10
Hanny 2100
Lizzie 1800
# 0
0

예제 출력

Race 1
Chris: 230
Karl: 180
Tania: 140
Race 2
Hanny: 20
Lizzie: 20

힌트