题目描述

译自 COI 2021 T1「Autobahn」

有 $N$ 个人在赛车场疾驰，第 $i$ 个人从第 $l_i$ 小时初疾驰到第 $r_i$ 小时末。

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

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

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

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

输入格式

第一行三个整数 $N$，$K$，$X$。

接下来 $N$ 行，一行三个整数 $l_i$，$t_i$，$r_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

数据范围与提示

对于 $100\%$ 的数据有 $1\le K\le N\le10^5$，$1\le X,l_i,t_i,r_i\le 10^9$，$l_i\le r_i$。