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

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，描述一段挤奶的时间。

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

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

USACO