광부 호석
시간 제한1초메모리 제한512 MB
한 꼭짓점이 (0,0)인 축에 평행한 직사각형 안의 광물 수가 C 이하가 되도록 고르고, 그 안 광물의 아름다움 합을 최대로 만든다.
문제
N개의 광물이 있다. i번째 광물은 (Xi, Yi)에 있고, 캐내는 비용은 1이며, 아름다운 정도는 Vi이다.
호석이는 지금 (0, 0)에 있다. 타고난 광부인 호석이는 시그니쳐 스킬인 "광산 뒤집기"를 쓰려고 한다. 이 스킬을 쓰면 자신이 있는 위치를 꼭짓점으로 하고 높이 H (H ≥ 0), 너비 W (W ≥ 0)인 직사각형 영역 안에 있는 모든 광물을 캘 수 있다. 영역의 테두리에 있는 광물도 캐야 한다.
직사각형 영역 안에 들어오는 광물은 무조건 캐야 하며, 영역에 속한 광물들의 캐내는 비용의 합이 현재 가진 돈 C보다 크면 파산한다.
호석이가 파산하면 광물을 캐지 못하고, 이로 인한 나비효과로 한국의 취업률이 떨어진다. 반대로 호석이가 얻는 광물들의 아름다운 정도의 합이 높아질수록 한국의 취업률은 올라간다. 모두의 행복을 위해 호석이가 파산하지 않고 얻을 수 있는 광물들의 아름다운 정도의 합을 최대화하자.
입력
첫 줄에 광물의 개수 N과 호석이가 가진 돈 C가 주어진다.
이어서 N개의 줄에 걸쳐 i번째 줄에 세 정수 Xi, Yi, Vi가 주어진다. 각 숫자는 i번째 광물의 X, Y 좌표와 아름다운 정도를 나타낸다.
출력
호석이가 파산하지 않으면서 얻을 수 있는 광물들의 아름다운 정도의 합의 최댓값을 출력하라.
제한
1 ≤ N ≤ 500,000
0 ≤ Xi, Yi ≤ 100,000
1 ≤ Vi ≤ 10^8
1 ≤ C ≤ N
모든 광물은 서로 다른 위치에 있고, (0, 0)에는 광물이 없다. 주어지는 모든 수는 정수이다.