Space Miner

Interview

Time limit2sMemory limit512 MB

Summary

Travel in straight segments through ordered 3D waypoints; for each planet, check whether any segment passes within distance ri+D of its center, then sum the resources of all planets you can reach at least once.

Level: Medium6 of 10
Topics: Geometry, Implementation, Math, Simulation
Solved: No attempts yet

Problem

There are $M$ planets ( $1 \le M \le 1{,}000$ ). Each planet $i$ holds $v_i$ ( $1 \le v_i \le 10{,}000$ ) units of resources and has radius $r_i$ ( $1 \le r_i \le 100$ ).

Starting from the origin $(0, 0, 0)$ , you travel in straight lines through $N$ ( $1 \le N \le 1{,}000$ ) waypoints in the given order.

At any moment during the trip, if your distance to a planet's center is at most $D + r_i$ ( $1 \le D \le 50$ ), you may mine that planet with your tractor beam and collect its $v_i$ units of resources. You can still mine a planet when you are exactly $D$ units from its surface (that is, exactly $r_i + D$ from its center). If your path passes through a planet, that is fine — your ship can drill straight through it, which only makes mining easier. However, once a planet has been mined you cannot mine it again, even if you pass by it later.

Output the total amount of resources you can mine during the journey.

Hint: perform all calculations with 64-bit integers.

Input

The first line contains the number of planets $M$ . Each of the next $M$ lines contains five integers $x_i\ y_i\ z_i\ v_i\ r_i$ describing a planet: planet $i$ is located at $(x_i, y_i, z_i)$ ( $-1{,}000 \le x_i, y_i, z_i \le 1{,}000$ ) and has $v_i$ resources and radius $r_i$ . The next line contains the number of waypoints $N$ . Each of the next $N$ lines contains a waypoint position as three integers $x_i\ y_i\ z_i$ ( $-1{,}000 \le x_i, y_i, z_i \le 1{,}000$ ). The last line contains $D$ , the maximum distance from a planet's surface at which your ship can still mine it.

Output

Output, on a single line, the total amount of resources you can mine during the journey.

Examples4

Example 1

Input

Expected output

Example 2
Input
```
1
0 0 0 100 1
1
5 0 0
1
```
Expected output
```
100
```
Example 3
Input
```
1
5 0 0 9 2
1
10 0 0
1
```
Expected output
```
9
```
Example 4
Input
```
1
5 3 0 7 1
1
10 0 0
2
```
Expected output
```
7
```