#P8387. [COI2021] Autobahn

[COI2021] Autobahn

题目描述

译自 COI 2021 T1「Autobahn

NN 个人在赛车场疾驰,第 ii 个人从第 lil_i 小时初疾驰到第 rir_i 小时末。

鉴于赛车场要恰钱,每疾驰一小时交一块钱,然而这 NN 个人都只付了前 tit_i 个小时的钱。

管理员十分仁慈,他们只会在有多余 KK 个人在赛车场上疾驰时来收额外的钱。

赛车场搞活动,要求划分出一个长为 XX 小时的时间段,在这个时间段内如果有人需要被补交钱,则他不需要补交对应时间段欠的钱。

赛车场希望活动使这 NN 个人不需要补交的钱最多,求出这个钱数。

输入格式

第一行三个整数 NNKKXX

接下来 NN 行,一行三个整数 lil_itit_irir_i

输出格式

仅输出一行一个整数,表示您的答案。

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

提示

【样例解释】

样例 #1 解释:

所划分出的时间段为 [4,7][4,7],这之中第一个人不需要交第 44 小时的费用,而第二、三、四个人不需要交第 6677 个小时的费用。

样例 #2 解释:

所划分出的时间段为 [12,33][12,33]

【数据范围】

对于 100%100\% 的数据有 1KN1051\le K\le N\le10^51X,li,ti,ri1091\le X,l_i,t_i,r_i\le 10^9liril_i\le r_i

Subtask 限制 分数
11 N,K,X,li,ti,ri100N,K,X,l_i,t_i,r_i\le 100 2020
22 N,K,X,li,ti,ri103N,K,X,l_i,t_i,r_i\le 10^3 3030
33 无特殊限制 5050