34081번 - 흰수염과 해적들

문제

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

— 에드워드 뉴게이트

무한한 크기의 좌표평면 위에 $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$)

출력

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

제한

힌트