Honest Worker

Interview

Time limit1sMemory limit1024 MB

Summary

Choose non-overlapping contractor jobs, each optionally quit early, to maximize total pay minus fake cover letter costs.

Level: Medium6 of 10
Topics: Dynamic programming, Sorting, Binary search
Solved: No attempts yet

Problem

Rafael lives in an ideal egalitarian society: all jobs offer identical payment rates, and you only have to work at a job that you find personally fulfilling. Unfortunately, even such a utopia cannot make up for the fact that Rafael is not very skilled at anything.

To compensate, Rafael turns to contractor work, where potential employers do not have the time to notice how unqualified he is for the job. Even so, since he lacks the qualifications for these contractor positions, he must spend money on fake cover letters just to get hired.

Rafael has a choice of $N$ contractor jobs. The $i$ -th job starts on day $\ell_i$ , ends at the end of day $r_i$ , and pays exactly $S$ gold coins per day. Rafael is a really bad worker and cannot work two jobs at the same time. He can start job $i$ only on day $\ell_i$ , but once hired, he may quit at the end of any day, keeping the money from the days he worked (including the last one). After quitting, he can start another job from the next day on, but not on the same day. A fake cover letter for job $i$ costs $c_i$ gold coins. Rafael always has enough savings to pay for any number of cover letters, even before working any of the $N$ jobs.

Given the jobs, what is the maximum profit Rafael can make after subtracting the cover letter costs?

Input

The first line contains two integers $N$ ( $1 \le N \le 10^6$ ) and $S$ ( $1 \le S \le 10^9$ ), the number of jobs and their daily pay. Each of the following $N$ lines contains three integers $\ell_i$ , $r_i$ , and $c_i$ ( $1 \le \ell_i \le r_i \le 10^9$ , $1 \le c_i \le 10^9$ ), the start date, end date, and cost of the fake cover letter for job $i$ .

Output

Output a single line with one integer: the amount of money Rafael can make after all the jobs are over.

Examples4

Example 1
Input
```
3 3
1 5 10
2 10 4
5 15 1
```
Expected output
```
37
```
Example 2
Input
```
3 5
1 1 3
2 3 4
3 3 1
```
Expected output
```
8
```
Example 3
Input
```
1 1000
1 1 654
```
Expected output
```
346
```
Example 4
Input
```
1 5
1 3 20
```
Expected output
```
0
```