흰수염과 해적들

시간 제한2초메모리 제한1024 MB

요약

원점에서 거리 L 이내의 점을 골라 능력을 쓰면 그 안의 해적이 기절하고 나머지는 바깥으로 1만큼 밀려난다. 이 과정을 반복해 얻는 현상금 합의 최댓값을 구한다.

난이도: 어려움10점 중 8점
유형: 기하, 그리디, 정렬, 수학
정답자: 아직 제출이 없습니다

문제

날 누구라고 생각하나, 난 흰수염이다..!

— 에드워드 뉴게이트

무한한 크기의 좌표평면 위에 $N$ 명의 해적이 있다. $i$ 번째 해적은 $(x\_i, y\_i)$ 에 존재하며, $c\_i$ 만큼의 현상금이 걸려있다. 서로 다른 두 해적이 같은 위치에 있는 경우는 없으며, 해적들의 위치는 $(0, 0)$ 이 아니다. 또한, 모든 $c\_i$ 는 양의 정수이다.

흰수염은 현재 $(0, 0)$ 에 있으며, 흔들흔들 열매의 능력을 사용하여 해적들을 기절시키려고 한다. 흔들흔들 열매 능력 범위는 $L$ 이며, 능력을 사용하면 다음과 같은 일이 순서대로 발생한다.

흰수염은 $\sqrt{x^2 + y^2} \leq L$ 을 만족하는 점 $(x,y)$ 를 고른다. 흰수염은 그 위치에 있는 모든 해적들을 흔들흔들 열매의 능력을 사용하여 기절시킨다. 선택한 $x,y$ 가 정수일 필요는 없다.
기절하지 않은 해적들은 공포에 질려 흰수염에게서 달아나려고 한다. 흰수염이 능력을 사용한 후, 기절하지 않은 모든 해적들은 각자 $(0, 0)$ 에서 가장 멀어지는 방향으로 정확히 $1$ 만큼 이동한다. 해적들이 이동을 완료한 위치가 정수 좌표가 아닐 수 있다.

흰수염이 능력을 원하는 만큼 사용했을 때, 흰수염이 기절시킨 해적들의 현상금의 총합의 최댓값을 구해보자!

입력

첫 번째 줄에 정수 $N$ , $L$ 이 공백으로 구분되어 주어진다. ( $1 \leq N \leq 500 \\, 000 ; 1 \leq L \leq 10^9$ )

두 번째 줄부터 $N$ 개의 줄에 걸쳐 $i$ 번째 해적의 좌표와 현상금을 나타내는 정수 $x\_i$ , $y\_i$ , $c\_i$ 가 공백으로 구분되어 주어진다. ( $0 \leq |x\_i|, |y\_i| \leq 10^9 ; (x\_i,y\_i) \neq (0,0); 1 \leq c\_i \leq 10^9$ )

출력

흰수염이 능력을 원하는 만큼 사용했을 때, 기절시킨 해적들의 현상금의 총합의 최댓값을 출력한다.

예제2

예제 1
입력
```
3 4
1 1 100
2 2 200
3 3 300
```
예상 출력
```
300
```
예제 2
입력
```
1 316405161
54645443 311650608 1
```
예상 출력
```
1
```