COI '20 #1 Autobahn

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

There are N people testing their racing cars on 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 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 what they have paid for. Administration of autobahn decided not to be very harsh and charge them only for those extra minutes in which there were at least K people on autobahn.

In a rush of generosity, administration decided to introduce happy hour i.e. interval of continuous X minutes for which they won't be paying extra charges. They picked happy hour so that the sum of extra charges that won't be paid is maximal possible. Determine that sum.

Input Specification

First line contains integers N, K and X (K \le N) from task description.

Next N lines contain integers l_i, t_i and r_i (l_i \le r_i) from task description.

Output Specification

Print the required sum in a single line.


Subtask Points Constraints
1 20 1 \le N,K,X,l_i,t_i,r_i \le 100
2 30 1 \le N,K,X,l_i,t_i,r_i \le 1\,000
3 50 1 \le N \le 10^5, 1 \le X,l_i,t_i,r_i \le 10^9

Sample Input 1

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

Sample Output 1


Explanation for Sample Output 1

Happy hour will span from 4th until the 7th minute. Inside that interval, first person should've paid extra for the 4th minute and second, third and fourth person should've paid for 6th and 7th minute.

Sample Input 2

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

Sample Output 2



There are no comments at the moment.