29993번 - Honest Worker 다국어

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 can’t account for the fact that Rafael is not very skilled at anything.

To compensate for this, Rafael turns to contractor work, where potential employers lack the time to realize how unqualified for the job he is. Even then, given his lack of qualifications for these contractor positions, he must expend money on acquiring fake cover letters in order to even get hired.

Rafael has a choice of N contractor jobs available to him. The i-th job starts at day ℓ_i, ends at the end of day r_i and pays exactly S gold coins a day. Rafael is a really bad worker, and cannot work two jobs at the same time; moreover, he can only start job i at day ℓ_i but, once hired, he can choose to quit at the end of any day, keeping the money from the days he worked (including the last one), and being able to start another job from the next day on, but not on the same day. Additionally, Rafael knows that it would cost c_i gold coins to buy a fake cover letter for job i. Aware of his inabilities and the need for fake cover letters, Rafael always has enough savings to pay for any number of cover letters he might need, even before working any of the N jobs.

Given the description of the available jobs, what is the maximum profit that Rafael can attain, factoring in the expenses for the required fake cover letters?

The first line contains two integers N (1 ≤ N ≤ 10⁶) and S (1 ≤ S ≤ 10⁹), representing the number of jobs available and what is their daily pay.

Each of the following N lines contains three integers: ℓ_i, r_i and c_i (1 ≤ ℓ_i ≤ r_i ≤ 10⁹, 1 ≤ c_i ≤ 10⁹), representing the start date, end date, and cost of obtaining a fake cover letter for job i, respectively.

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