题目描述

贝茜是一只非常努力工作的奶牛，她总是专注于提高自己的产量。为了产更多的奶，她预计好了接下来的$\red{N (1 ≤}$ $\red{N ≤}$ $\red{1,000,000)}$个小时，标记为$\red{0..N-1}$。

$\red{Farmer John }$计划好了 $\red{M (1 ≤}$ $\red{M ≤}$ $\red{1,000) }$个可以挤奶的时间段。每个时间段有一个开始时间$\red{(0 ≤}$ 开始时间 $\red{≤}$ $\red{N), }$和一个结束时间 $\red{(}$开始时间 $\red{< }$结束时间 $\red{≤}$ $\red{N), }$和一个产量 $\red{(1 ≤}$ 产量 $\red{≤}$ $\red{1,000,000) }$表示可以从贝茜 挤奶的数量。

$\red{Farmer John }$从分别从开始时间挤奶，到结束时间为止。每次挤奶必须使用整个时间段。 但即使是贝茜也有她的产量限制。每次挤奶以后，她必须休息 $\red{R (1 ≤}$ $\red{R ≤}$ $\red{N) }$个小时才能下次挤奶。

给定$\red{Farmer John }$计划的时间段，请你算出在 $\red{N }$个小时内，最大的挤奶的量。

输入格式

第$\red{1}$行三个整数$\red{N，}$$\red{M，}$$\red{R.}$

接下来$\red{M}$行，每行三个整数$\red{S_i，}$$\red{E_i，}$$\red{P_i}$．

输出格式

最大产奶量．

样例

输入样例

12 4 2

1 2 8

10 12 19

3 6 24

7 10 31

输出样例

43

提示

注意：结束时间不挤奶