정직한 노동자

면접 대비

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

요약

겹치지 않게 계약직 일을 고르고 각 일을 중간에 그만둘 수 있을 때, 급여에서 추천서 비용을 뺀 최대 이익을 구합니다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 정렬, 이분 탐색
정답자: 아직 제출이 없습니다

문제

라파엘은 평등한 이상 사회에 산다. 모든 직업의 임금이 같고, 자신이 보람을 느끼는 일만 하면 된다. 안타깝게도 이런 유토피아도 라파엘이 어떤 분야에서든 뛰어나지 않다는 사실을 메워 주지는 못한다.

이를 보완하려고 라파엘은 계약직 일을 찾는다. 계약직 고용주들은 그가 그 일에 얼마나 자격이 없는지 알아볼 시간이 없다. 그래도 계약직 자리에 필요한 자격이 없으므로, 채용되려면 가짜 지원서를 사는 데 돈을 써야 한다.

라파엘에게는 $N$ 개의 계약직 일 중 고를 수 있는 선택지가 있다. $i$ 번째 일은 $\ell_i$ 일에 시작하고, $r_i$ 일의 끝에 끝나며, 하루에 정확히 $S$ 골드 코인을 준다. 라파엘은 매우 일을 못하며, 두 일을 동시에 할 수 없다. 일 $i$ 는 $\ell_i$ 일에만 시작할 수 있다. 하지만 일단 채용되면 아무 날의 끝에서나 그만둘 수 있고, 일한 날들(마지막 날 포함)의 급여는 그대로 받는다. 그만둔 다음에는 다음 날부터 다른 일을 시작할 수 있지만, 같은 날에는 시작할 수 없다. 일 $i$ 의 가짜 지원서를 사는 데는 $c_i$ 골드 코인이 든다. 라파엘은 $N$ 개의 일을 하기 전에도 지원서를 몇 장이든 살 만큼의 돈을 항상 가지고 있다.

일이 주어졌을 때, 지원서 비용을 빼고 라파엘이 얻을 수 있는 최대 이익은 얼마인가?

입력

첫 줄에 두 정수 $N$ ( $1 \le N \le 10^6$ )과 $S$ ( $1 \le S \le 10^9$ )가 주어진다. 각각 일의 개수와 하루 급여이다. 이어지는 $N$ 개의 줄에는 세 정수 $\ell_i$ , $r_i$ , $c_i$ ( $1 \le \ell_i \le r_i \le 10^9$ , $1 \le c_i \le 10^9$ )가 주어진다. 각각 일 $i$ 의 시작일, 종료일, 가짜 지원서 비용이다.

출력

라파엘이 모든 일을 마친 후 벌 수 있는 금액을 정수 하나로 한 줄에 출력한다.

예제4

예제 1
입력
```
3 3
1 5 10
2 10 4
5 15 1
```
예상 출력
```
37
```
예제 2
입력
```
3 5
1 1 3
2 3 4
3 3 1
```
예상 출력
```
8
```
예제 3
입력
```
1 1000
1 1 654
```
예상 출력
```
346
```
예제 4
입력
```
1 5
1 3 20
```
예상 출력
```
0
```