Race

There are n checkpoints. Each runner starts at the origin (0, 0), visits any subset of the checkpoints, and returns to the origin. The visited checkpoint numbers must be in increasing order. If the checkpoints are numbered from 1 to n, visiting 1, 2, 5 in that order is allowed, but visiting 4 and then 2 is not.

Every move must follow the straight segment between two points. If another checkpoint lies on that segment, the runner may either count it as visited or pass it by. A checkpoint's score can be earned at most once.

Each runner has a maximum distance d they can run. Compute the maximum score the runner can earn while still returning to the origin within that limit.

The input consists of multiple test cases. Each test case has the following format, and the entire input ends with a single line containing 0.

• The first line contains the number of checkpoints n (1 <= n <= 30).
• The next n lines each contain three integers x, y, and s: the checkpoint coordinates and score (-5000 <= x, y <= 5000, 10 <= s <= 200).
• Then several runner lines follow. Each line contains a runner name and a maximum distance d separated by a space (0 <= d <= 10000). A name has at most 60 characters and contains no spaces.
• The line # 0 marks the end of the runner list for the current test case.

All distances are straight-line distances in the plane.

For each test case, first print Race r, where r is the test case number starting from 1.

Then, for each runner in input order, print one line in the format name: score.