21279번 - 광부 호석 출처전체 채점분류

N 개의 광물이 있다. i 번째 광물은 (X_i , Y_i )에 있으며 캐내는 비용은 1이고, 이것의 아름다운 정도는 V_i 이다.

호석이는 지금 (0, 0)에 있다. 타고난 광부인 호석이는 시그니쳐 스킬인 "광산 뒤집기"를 쓰려고 한다. 이 스킬을 쓰면 자신이 있는 위치를 꼭지점으로 하며, 원하는 높이 H(H ≥ 0), 너비 W(W ≥ 0) 인 직사각형 영역 안에 있는 모든 광물을 캘 수 있다. 영역의 테두리에 존재하는 광물도 캐야한다.

주의할 점은, 직사각형 영역 안에 들어오는 광물은 무조건 캐야 하며, 영역에 속한 광물들의 캐내는 비용의 총합이 현재 가진 돈 C 보다 크면 파산을 하게 된다.

호석이가 파산하면 광물을 못 캐고, 이로 인해 상상을 초월하는 나비효과가 발생해서 한국의 취직율이 떨어진다!!!!!!! 대신 호석이가 얻을 수 있는 광물들의 아름다운 정도의 합이 높아질수록 한국의 취직율은 올라간다!!!!!!!! 모두의 행복을 위해서 호석이가 파산하지 않고 얻을 수 있는 광물들의 아름다운 정도를 최대화하자.

첫 줄에 광물의 개수 N 과 호석이가 가진 돈 C 가 주어진다.

이어서 N개의 줄에 걸쳐서, i번째 줄에 3개의 정수 X_i , Y_i , V_i 가 주어진다. 각 숫자는 i 번째 광물이 위치한 X, Y 좌표와 아름다운 정도를 의미한다.

호석이가 파산하지 않으면서 얻을 수 있는 광물들의 아름다운 정도의 합의 최댓값을 출력하라.

1 ≤ N ≤ 500,000 

0 ≤ X_i , Y_i​ ≤ 100,000

1 ≤ V_i ≤ 10⁸

1 ≤ C ≤ N

광물들은 모두 서로 다른 위치에 존재하며, (0, 0) 에는 광물이 존재하지 않음이 보장된다. 주어지는 모든 수는 정수이다.