题目描述

Bessie 可以在接下来 $N$ 个小时内产奶，为了方便，我们把这 $N$ 个小时 $0\dots N-1$ 编号。

FJ 在这 $N$ 个小时内有 $M$ 段时间可以来给 Bessie 挤奶，第 $i$ 段时间从 $Start_i$ 开始到 $End_i$ 结束，可以得到 $Eff_i$ 加仑牛奶。

每次 FJ 给 Bessie 挤奶之后，Bessie 都要休息 $R$ 个小时，FJ 才能开始下一次挤奶。

现在，FJ 需要您计算出 Bessie 在这 $N$ 个小时内最多产多少奶。

输入格式

第一行有三个整数，分别表示 $N,M,R$。

第 $2\dots M+1$ 行，第 $i+1$ 行有三个整数 $Start_i,End_i,Eff_i$，描述一段挤奶的时间。

输出格式

输出一行一个整数表示答案。

12 4 2
1 2 8
10 12 19
3 6 24
7 10 31

43

提示

数据规模与约定

对于全部的测试点，保证 $1\le N\le 10^6$，$1\le M\le 10^3$，$1\le Start_i<end_i\le N$，$1\le Eff_i\le 10^6$。