题目描述

一个节日将在一个小镇的主街上举行。主街有 $n$ 个区段。这些区段从左到右编号为 $1$ 到 $n$。两个相邻区段之间的距离为 $1$。

在节日里，将会有 $m$ 个烟花被放入空中。第 $i$ 次（$1<=i<=m$）放烟花的时间是 $t_{i}$，在 $a_{i}$ 区段。如果你在第 $i$ 次放烟花的时候，处于 $x$ 区段（$1<=x<=n$），你将会获得幸福值 $b_{i}-|a_{i}-x|$（注意，幸福值可能是负数）。

你可以在一个单位时间内移动最多 $d$ 个长度单位，但是禁止走出主街。你可以在初始时间（时间等于 $1$）在任意区段，你的目的是最大化从观看烟花中获得的幸福值之和。找到最大的总幸福值。

注意，两个或更多的烟花可以在同一时间放出。

输入格式

第一行包含三个整数 $n$，$m$，$d$ （$1<=n<=150000; 1<=m<=300; 1<=d<=n$）。

接下来的 $m$ 行，每行包含整数 $a_{i}$，$b_{i}$，$t_{i}$ （$1<=a_{i}<=n; 1<=b_{i}<=10^{9}; 1<=t_{i}<=10^{9}$）。第 $i$ 行包含第 $i$ 次放烟花的描述。

数据保证满足条件 $t_{i}<=t_{i+1}$（$1<=i<m$）。

输出格式

打印一个整数，表示你可以从观看所有烟花中获得的最大幸福值之和。

样例 #1

样例输入 #1

50 3 1
49 1 1
26 1 4
6 1 10

样例输出 #1

-31

样例 #2

样例输入 #2

10 2 1
1 1000 4
9 1000 4

样例输出 #2

1992