当前没有测试数据。

4.火车载客

题目描述

一辆单趟火车，从$1$号站一直驶向$N$号站，可以看做在一数轴上，依次排列着$1$到$N$号站。火车一次最多只能坐$C$个人。如果客满了只有等乘客下车后才能承载新的乘客。现在有$K$组人，每组人的人数为$p$，他们想在$s_i$号站上车，$t_i$号站下车。

你的任务是合理的选择让哪些乘客上车，使得尽可能多的乘客完成行程。可以只让一组中的一部分人上车。

输入格式

第一行三个整数$K$，$N$，$C$含义与题目描述相同。

接下来$K$行，每行给出了每一组人的信息：$s_i$，$t_i$，$p_i$，含义与题目描述相同。

输出格式

输出一个整数表示最多能满足多少乘客的行程。

数据范围与提示

• 对于$60\%$的数据，$1 \leq N$，$K \leq 5000$；
• 对于$100\%$的数据，$1 \leq N \leq 3 \times 10^5$，$C \leq 100$，$1 \leq s_i < t_i \leq N$。

样例

8 15 3
1 5 2
13 14 1
5 8 3
8 14 2
14 15 1
9 12 1
12 15 2
4 6 1

10