M ( 1 ≤ M ≤ 1000) 개의 행성에 vi ( 1 ≤ vi ≤ 10000 ) 만큼의 자원이 있고 각 행성의 반지름은 ri ( 1 ≤ ri ≤ 100 ) 이다.

(0, 0, 0)에서 시작해 직선으로 총 N ( 1 ≤ N ≤ 1000 ) 개의 지점을 통과해가게 된다.

만약 행성의 중심과 D ( 1 ≤ D ≤ 50 ) + ri 만큼 떨어져 있다면 레이저 트랙터를 이용해 vi만큼의 자원을 캐올 수 있다. (행성의 표면으로부터 정확히 D만큼 떨어져 있어도 자원을 캘 수 있음에 유의) 우리가 타고 있는 우주선은 행성을 통과해갈 수 있는 장치가 마련되어 있으니 혹시 루트가 행성을 통과하게 돼도 걱정할 필요는 없다. 또한, 한 행성을 두 번 방문하게 되더라도 자원은 단 한 번만 캘 수 있다.

자원 채취 루트가 주어졌을 때 캘 수 있는 자원의 양을 구하세요.

힌트: 64비트 정수형을 사용해야 합니다.

입력

• 첫째 줄에는 M (행성의 개수)가 입력된다.
• 다음 M 개의 줄은 각 행성의 정보를 준다. 순서대로 x, y, z좌표, vi, ri 이다.
• 다음 줄에는 통과해야 하는 지점의 좌표의 개수 N이 입력된다.
• 다음 N 개의 줄에는 통과해야 하는 좌표가 입력된다. (x, y, z)
• 다음 줄에는 자원을 채취할 수 있는 거리, D가 입력된다.

출력

입출력 예

입력

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

출력

5 

출처:http://cemc.uwaterloo.ca/contests/computing/2010/stage2/day2.pdf 
추천:KOINICHI