Canadian Computing Competition: 2010 Stage 2, Day 2, Problem 2

There are $M$ $(1\le M\le 1000)$ planets each with $v_i$ $(1\le v_i\le 10000)$ units of resources and radius $r_i$ $(1\le r_i\le 100)$.

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

Whenever you travel within $D+r_i$ $(1\le D\le 50)$ units from a planet's centre, you can mine the planet using your tractor beam retrieving $v_i$ 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.

Hint: you should do all calculations with 64-bit integers.

Input Specification

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 $x_i{y}_i{z}_i{v}_i{r}_i$, where the planet $i$ is at position $(x_i,y_i,z_i)$, (where $-1000\le x_i,y_i,z_i\le 1000$) and this planet has $v_i$ resources and radius $r_i$. On the next line is the number $N$, the number of waypoints to pass through. Each of the next $N$ lines contains the position of these waypoints, as three integers $x_i{y}_i{z}_i$ $(-1000\le x_i,y_i,z_i\le 1000)$. 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 Specification

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