题目描述

译自 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

提示

【样例解释】

样例 #1 解释：

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

样例 #2 解释：

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

【数据范围】

对于 $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$。