Problem Description

Translated from COI 2021 T1 “Autobahn”

There are $N$ people racing on a track. Person $i$ races from the beginning of hour $l_i$ to the end of hour $r_i$.

Since the track wants to make money, it charges one unit of money for each hour of racing. However, these $N$ people have only paid for the first $t_i$ hours.

The administrators are very kind: they will only come to collect additional money when there are at least $K$ people racing on the track.

The track runs a promotion: it must choose a time interval of length $X$ hours. During this interval, if someone would need to pay extra money, then they do not need to pay the unpaid money corresponding to this interval.

The track wants this promotion to maximize the total amount of money that these $N$ people do not need to pay extra. Find this maximum amount.

Input Format

The first line contains three integers $N$, $K$, and $X$.

The next $N$ lines each contain three integers $l_i$, $t_i$, and $r_i$.

Output Format

Output a single integer, the answer.

5 3 4
2 1 4
3 3 7
3 3 8
1 5 7
5 3 8

7

3 2 22
7 16 33
69 14 88
8 10 97

27

Hint

[Sample Explanation]

Sample #1 explanation:

The chosen interval is $[4,7]$. In it, the first person does not need to pay the fee for hour $4$, and the second, third, and fourth people do not need to pay the fees for hours $6$ and $7$.

Sample #2 explanation:

The chosen interval is $[12,33]$.

[Constraints]

For $100\%$ of the testdata, $1\le K\le N\le 10^5$, $1\le X,l_i,t_i,r_i\le 10^9$, and $l_i\le r_i$.

Translated by ChatGPT 5