A - Watching the Fireworks Festival Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君は花火大会の会場にいます。 2 次元平面上に N 個の花火の打ち上げ地点があり、 i 番目の花火は座標 (X_i, Y_i) から打ち上げられます。 i 番目の花火を観覧できた場合、満足度が P_i 得られます。

高橋君は座標 (X_A, Y_A) の地点に立っています。高橋君は、自分の立っている地点からのユークリッド距離が R 以下であるような打ち上げ地点の花火をすべて観覧することができます。

高橋君が観覧できる花火の満足度の合計を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • -10^9 \leq X_A, Y_A \leq 10^9
  • 0 \leq R \leq 10^9
  • -10^9 \leq X_i, Y_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq P_i \leq 10^4 (1 \leq i \leq N)
  • 入力はすべて整数

入力

N X_A Y_A R
X_1 Y_1 P_1
X_2 Y_2 P_2
:
X_N Y_N P_N
  • 1 行目には、花火の個数を表す N 、高橋君の位置の X 座標を表す X_A 、 Y 座標を表す Y_A 、および観覧可能な範囲の半径を表す R がスペース区切りで与えられる。
  • 2 行目から N 行では、各花火の情報が与えられる。
  • 1 + i 行目では、 i 番目の花火の打ち上げ地点の X 座標を表す X_i 、 Y 座標を表す Y_i 、およびその花火の満足度を表す P_i がスペース区切りで与えられる。

出力

高橋君が得られる満足度の合計を 1 行に出力してください。

入力例 1

4 0 0 5
3 4 10
5 0 20
6 0 30
-1 -1 5

出力例 1

35

入力例 2

3 10 10 2
0 0 100
13 10 200
10 13 300

出力例 2

0

入力例 3

10 -2 3 10
-2 3 50
8 3 70
-12 3 80
-2 14 90
4 9 30
-9 -1 40
20 20 100
-5 -6 60
6 -3 25
-11 10 35

出力例 3

355

入力例 4

30 100000000 -100000000 500000000
100000000 -100000000 100
600000000 -100000000 200
-400000000 -100000000 300
100000000 400000000 400
100000000 -600000000 500
450000000 250000000 600
500000000 200000000 700
700000000 -100000000 800
100000000 500000000 900
-100000000 -300000000 1000
300000000 -500000000 1100
-200000000 200000000 1200
400000000 -400000000 1300
-300000000 100000000 1400
200000000 100000000 1500
-350000000 -250000000 1600
550000000 -250000000 1700
250000000 -550000000 1800
-100000000 -550000000 1900
-450000000 -100000000 2000
1000000000 1000000000 2100
-1000000000 -1000000000 2200
999999999 -999999999 2300
-999999999 999999999 2400
123456789 -123456789 2500
-123456789 123456789 2600
400000000 300000000 2700
-250000000 -450000000 2800
550000000 150000000 2900
-300000000 -400000000 3000

出力例 4

30900

入力例 5

1 1000000000 -1000000000 0
1000000000 -1000000000 10000

出力例 5

10000

Score : 266 pts

Problem Statement

Takahashi is at a fireworks festival venue. There are N firework launch points on a 2-dimensional plane, and the i-th firework is launched from coordinates (X_i, Y_i). If Takahashi can watch the i-th firework, he gains a satisfaction of P_i.

Takahashi is standing at the point with coordinates (X_A, Y_A). Takahashi can watch all fireworks whose launch points have a Euclidean distance of R or less from the point where he is standing.

Find the total satisfaction of the fireworks that Takahashi can watch.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • -10^9 \leq X_A, Y_A \leq 10^9
  • 0 \leq R \leq 10^9
  • -10^9 \leq X_i, Y_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq P_i \leq 10^4 (1 \leq i \leq N)
  • All inputs are integers

Input

N X_A Y_A R
X_1 Y_1 P_1
X_2 Y_2 P_2
:
X_N Y_N P_N
  • The first line contains N representing the number of fireworks, X_A representing the X coordinate of Takahashi's position, Y_A representing the Y coordinate, and R representing the radius of the viewable range, separated by spaces.
  • From the 2nd line to the next N lines, the information for each firework is given.
  • The (1 + i)-th line contains X_i representing the X coordinate of the i-th firework's launch point, Y_i representing the Y coordinate, and P_i representing the satisfaction of that firework, separated by spaces.

Output

Output the total satisfaction that Takahashi can obtain in a single line.

Sample Input 1

4 0 0 5
3 4 10
5 0 20
6 0 30
-1 -1 5

Sample Output 1

35

Sample Input 2

3 10 10 2
0 0 100
13 10 200
10 13 300

Sample Output 2

0

Sample Input 3

10 -2 3 10
-2 3 50
8 3 70
-12 3 80
-2 14 90
4 9 30
-9 -1 40
20 20 100
-5 -6 60
6 -3 25
-11 10 35

Sample Output 3

355

Sample Input 4

30 100000000 -100000000 500000000
100000000 -100000000 100
600000000 -100000000 200
-400000000 -100000000 300
100000000 400000000 400
100000000 -600000000 500
450000000 250000000 600
500000000 200000000 700
700000000 -100000000 800
100000000 500000000 900
-100000000 -300000000 1000
300000000 -500000000 1100
-200000000 200000000 1200
400000000 -400000000 1300
-300000000 100000000 1400
200000000 100000000 1500
-350000000 -250000000 1600
550000000 -250000000 1700
250000000 -550000000 1800
-100000000 -550000000 1900
-450000000 -100000000 2000
1000000000 1000000000 2100
-1000000000 -1000000000 2200
999999999 -999999999 2300
-999999999 999999999 2400
123456789 -123456789 2500
-123456789 123456789 2600
400000000 300000000 2700
-250000000 -450000000 2800
550000000 150000000 2900
-300000000 -400000000 3000

Sample Output 4

30900

Sample Input 5

1 1000000000 -1000000000 0
1000000000 -1000000000 10000

Sample Output 5

10000