Autobahn

Time limit1sMemory limit512 MB

Summary

Each driver stays for a time interval and owes extra fees for minutes when at least K drivers are present; choose X consecutive minutes to waive fees and maximize the waived total.

Level: Hard8 of 10
Topics: Prefix sum, Sliding window, Sorting, Implementation
Solved: No attempts yet

Problem

There are $N$ people testing their racing cars on the notorious autobahn, where limits do not exist. In this task, however, limits do exist. So we kindly ask you to restrain yourself from submitting exponential complexity solutions.

Person $i$ came to the autobahn at the beginning of minute $l_i$ , paid for $t_i$ minutes of stay, and left at the end of minute $r_i$ . Unfortunately some stayed for longer than they paid for. The administration of the autobahn decided not to be very harsh and charge them only for those extra minutes in which there were at least $K$ people on the autobahn.

In a rush of generosity, the administration decided to introduce a happy hour, that is, an interval of $X$ continuous minutes for which they will not be paying extra charges. They picked the happy hour so that the sum of extra charges that will not be paid is maximal possible. Determine that sum.

Input

The first line contains the integers $N$ , $K$ , and $X$ from the task description ( $K \le N$ ).

The next $N$ lines contain the integers $l_i$ , $t_i$ , and $r_i$ from the task description ( $l_i \le r_i$ ).

Output

Print the required sum in a single line.

Hint

First sample explanation: The happy hour will span from the 4th minute until the 7th minute. Inside that interval, the first person should have paid extra for the 4th minute, and the second, third, and fourth person should have paid for the 6th and 7th minute.

Examples2

Example 1
Input
```
5 3 4
2 1 4
3 3 7
3 3 8
1 5 7
5 3 8
```
Expected output
```
7
```
Example 2
Input
```
3 2 22
7 16 33
69 14 88
8 10 97
```
Expected output
```
27
```