2010 Canadian Computing Competition, Stage 2

Day 2, Problem 2: Space Miner

There are M (1 ≤ M ≤ 1000) planets each with vi (1 ≤ vi ≤ 10000) units of resources and radius ri (1 ≤ ri ≤ 100).

Starting from (0,0,0), you travel in straight lines through N (1 ≤ N ≤ 1000) waypoints in a specific order.

Whenever you travel within D+ri (1 ≤ D ≤ 50) units from a planet's center, you can mine the planet using your tractor beam retrieving vi units of resources. Note that if you are exactly D units from the surface of the planet, you can mine the planet. If your path takes you through a planet, do not worry, since your spaceship can drill through planets, which makes mining even easier. Also note that you cannot mine the same planet on a subsequent visit.

Give the number of minerals that can be mined on your journey.

Input

On the first line of input is the number M, the number of planets. On the next M lines are five integers describing each of the M planets. These integers are xiyiziviri, where the planet i is at position (xi,yi,zi), (where -1000 ≤ xi, yi, zi ≤ 1000).

After the M planets, there is line containing the integer N, followed by N lines (each with three integers x, y, and z) describing the points on your route in order.

The last line of input is the number D, the maximum distance from a planet's surface that your ship can be and still mine a planet.

Output

On one line, output the amount of minerals that you can mine on your journey.

Sample Input

3
10 0 0 1 1
0 10 0 2 1
0 0 10 4 1
3
8 0 0
0 7 0
0 0 9
1

Sample Output

5

All Submissions
Best Solutions


Point Value: 15
Time Limit: 2.00s
Memory Limit: 256M
Added: May 19, 2010

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

The input description is incomplete:

After the M planets, there's a line with the integer N, followed by N lines (each with 3 integers, x, y, and z) describing the points on your route in order.

You should be able to edit the problem description on the Judge machine directly now through ssh

Posting clarification comments is faster =P

Ugh, fine, I'll do it.

The input description of this problem is somehow incorrect...