거위에게 먹이 주기

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

요약

각 거위의 대기 구간과 속도 등급을 고려해 먹이를 줄 거위를 고르고, 귀여움 점수 합의 최댓값을 구합니다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 세그먼트 트리, 정렬, 구간
정답자: 아직 제출이 없습니다

문제

KAIST 캠퍼스에는 $N$ 마리의 사랑스러운 거위가 있다. KAIST는 이 거위들을 축하하려고 학생들을 위한 KAIST 거위 쇼를 연다. 쇼의 주된 내용은 거위에게 먹이를 주고 거위들이 보이는 즐거운 반응을 감상하는 것이다.

여러분은 대표 먹이 주는 사람으로 뽑혔다. 쇼가 최대한 귀엽게 되도록 거위에게 최적으로 먹이를 주는 것이 임무다. $i$ 번째 거위는 시각 $T_i$ 에 다가와서 $L$ 의 기간 동안 먹이를 기다린다. 정확히는 $i$ 번째 거위는 $T_i\le x\le T_i+L$ 인 시간 구간에 먹이를 먹을 수 있다. 시각 $T_i+L$ 이 지나면 거위는 흥미를 잃고 떠난다.

$i$ 번째 거위의 속도 수준은 $A_i$ 이고 귀여움은 $C_i$ 이다. 어느 시각에든 먹이를 던지면, 기다리고 있는 거위 중 가장 빠른 거위(가장 큰 $A_i$ )가 먹이를 가져간다. 그 거위는 자신의 귀여움을 뽐내며, $C_i$ 가 쇼의 전체 귀여움 점수에 더해진다. 먹이를 먹은 거위는 만족하고 떠난다. 속도 수준이 같은 거위는 없다. 잡음을 내는 거위도 있어서 $C_i$ 는 음수일 수 있다.

먹이는 원하는 만큼 던질 수 있으며, 던지는 빈도나 양에 제한은 없다. 쇼가 얻을 수 있는 최대 귀여움 점수를 구하라.

입력

첫 줄에 공백으로 구분된 두 정수 $N$ 과 $L$ 이 주어진다.

다음 $N$ 개 줄에는 각각 공백으로 구분된 세 정수 $A_i$ , $C_i$ , $T_i$ 가 주어진다.

출력

쇼의 최대 귀여움 점수를 출력한다.

제한

$1\le N\le 300\,000$
$1\le L\le 10^9$
$1\le A_i\le N\ (1\le i\le N)$
$i\neq j$ 이면 $A_i\neq A_j\ (1\le i,j\le N)$
$-10^9\le C_i\le 10^9\ (1\le i\le N)$
$0\le T_i\le 10^9\ (1\le i\le N)$
입력의 모든 값은 정수이다.

예제1

예제 1

입력

예상 출력