시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 303 91 42 18.834%

문제

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

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

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

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

입력

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

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

출력

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

제한

1 ≤ N ≤ 500,000 

0 ≤ X, Yi​ ≤ 100,000

1 ≤ Vi ≤ 108

1 ≤ C ≤ N

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

예제 입력 1

5 3
1 10 10
2 4 1
3 8 10
4 5 5
5 7 6

예제 출력 1

21


 

예제 입력 2

4 2
1 1 1
1 4 1
4 1 1
4 4 1

예제 출력 2

2


 

채점 및 기타 정보

  • 14개 이상의 데이터를 맞아야 를 받는다.