题目描述
一辆单趟火车，从 $1$ 号站一直驶向 $N$ 号站，可以看做在一数轴上，依次排列着 $1$ 到 $N$ 号站。火车一次最多只能坐 $C$ 个人。如果客满了只有等乘客下车后才能承载新的乘客。现在有 $K$ 组人，每组人的人数为 $p_i$，他们想在 $s_i$ 号站上车，$t_i$ 号站下车。
你的任务是合理的选择让哪些乘客上车，使得尽可能多的乘客完成行程。可以只让一组中的一部分人上车。
输入
第一行三个整数 $K,N,C$ 含义与题目描述相同。
接下来 $K$ 行，每行给出了每一组人的信息：$s_i,t_i,p_i$ 含义与题目描述相同。
输出
输出一个整数表示最多能满足多少乘客的行程。
样例输入输出
输入#1
复制
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
提示
对于 $60\%$ 的数据，$1 \leq N,K \leq 5000$。
对于 $100\%$ 的数据，$1\leq N \leq 300000$，$C \leq 100$，$1 \leq s_i < t_i \leq N$。