题目描述

机器可以在接下来的 $N$ 个小时内工作，共有 $M$ 个可选生产时段。选择第 $i$ 个时段后，机器会从第 $S_i$ 小时工作到第 $E_i$ 小时，并生产 $C_i$ 个单位的产品。

如果先选择时段 $i$，再选择时段 $j$，必须满足 $S_j-E_i \ge T$，其中 $T$ 是机器所需的冷却时间。

请从给出的时段中选择若干个，使生产总量最大。

输入格式

第一行包含三个整数 $N,M,T$，分别表示总时长、可选生产时段数量和冷却时间。

接下来 $M$ 行，每行包含三个整数 $S_i,E_i,C_i$，分别表示一个生产时段的开始时间、结束时间和产量。

输出格式

输出一个整数，表示能够生产的最大产品总量。

20 5 2
1 2 8
10 15 10
4 6 30
7 10 35
16 20 15

58

数据范围与提示

• $1 \le N \le 10^6$
• $1 \le M \le 10^3$
• $1 \le S_i < E_i \le N$
• $1 \le C_i \le 10^6$
• $0 \le T \le N$