题目背景

农场主约翰在未来 $N$ 个小时内可以给奶牛贝茜挤奶。为了方便，我们将这 $N$ 个小时编号为 $0 \dots N - 1$。

题目描述

在这 $N$ 个小时内，约翰有 $M$ 个可以挤奶的时间段。第 $i$ 个时间段从 $Start_i$ 到 $End_i$，可产奶 $Eff_i$ 加仑。

每次挤奶后，贝茜必须休息 $R$ 个小时，约翰才能开始下一次挤奶。

现在，约翰需要你计算在这些 $N$ 个小时内贝茜最多能产多少加仑牛奶。

输入格式

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

第 $2 \sim 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$，$0 \le Start_i \lt End_i \le N - 1$，且 $1 \le Eff_i \le 10^6$。