疯狂的bLue

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

众所周知神秘的 ACM 实验室有一个史诗级的出题狂魔,名曰 bLue。最近 bLue 又露出了邪恶的笑,原来是 bLue 接了为校赛出题的单子。

距离校赛开始还有 N 小时,由于各种奇怪的原因出题组可以出题的时间并不固定,大致可以分为M个时间段。每个时间段可以出的题目数也可能不同。同时由于出题是个煞费心血的事情,所以每个出题时间段结束后,善良的 bLue 会让大家休息 R (1 ≤ R ≤ N ) 小时,以便为接下来的出题事业继续奋斗。

为了能为校赛准备尽可能多的题目以备不时之需,bLue 需要好好地规划好这 N 小时如何安排,当然作为唯一的长者,bLue 一下子就为大家规划好了如何安排出题的时间段。

现在 bLue 想考考你在他完美的安排下出题组最多可以出多少个题目?

Input

测试数据有多组,输入直到文件结束。

对于每组数据:

  • 第一行输入三个数 N (1 ≤ N ≤ 1,000,000), M (1 ≤ M ≤ 1,000), R (1 ≤ R ≤ N)
  • 接下来有 M 行输入,每一行输入三个数 Si (0 ≤ Si < N), Ei (Si < Ei ≤ N) ,Vi (1 ≤ Vi ≤ 1,000,000) (0 < i <= M),分别表示为第 i 个时间段的开始时间,第 i 段的结束时间,第 i 个时间段可以出的题目数

Output

对于每组数据,输出出题组最多可以出的题的数目。

Sample Input

15 5 3
1 4 5
6 9 4
3 5 2
7 10 8
11 15 2

Sample Output

13

Hint

假设出题组在第 5 小时出完了一个时间段的题,他们需要休息 3 小时 (R = 3),那么他们在第 8 小时又可以继续开始出题了。

Source

【“师创杯”山东理工大学第九届ACM程序设计竞赛 热身赛】Ninaye