当前没有测试数据。

题目描述

某工厂正在进行生产调度，工厂的机器可以在接下来的 $N$ 个小时内进行工作。

工厂有 $M$ 个可用的生产时段，第 $i$ 个时段从第 $S_i$ 小时开始，到第 $E_i$ 小时结束。在这个时段内，机器能够生产 $C_i$ 个单位的产品。

由于机器每次工作后需要冷却一段时间，厂长规定，如果本次生产在第 $E_i$ 小时结束，那么下一次的生产的开始时间 $S_{i+1}$ 和本次生产时间的结束时间 $E_i$ 的差值，要满足 $S_{i+1} - E_i \ge T$，以保证机器有充分的时间散热，不会因为连续生产导致损坏。

你的任务是帮助工厂安排生产时段，使得在这 $N$ 个小时内，工厂能够生产的产品总量最大。

你只需编程计算出，工厂在这 $N$ 个小时内，最多可以生产多少个单位的产品。

输入格式

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

接下来 $M$ 行，每行包含三个整数 $S_i$、$E_i$ 和 $C_i$，表示第 $i$ 段生产时段的起始小时、结束小时以及在该时段内能够生产的产品数量。

输出格式

输出一个整数，表示工厂在 $N$ 个小时内能够生产的最大产品总量。

样例

输入

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

输出

58

数据范围

对于 $40\%$ 的测试数据，满足 $1 \le N \le 1000$，$1 \le M \le 100$。

对于 $100\%$ 的测试数据，满足 $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$。