题目描述

一个城镇有 $n$ 个区域，从左到右编号为 $1\sim n$，个区域之间距离 $1$ 个单位距离。

有 $m$ 个烟火要放，给定放的地点 $a_i$，时间 $t_i$，如果你当时在区域 $x$，那么你可以获得 $b_i - \vert a_i - x\vert$ 的开心值。

你每个单位时间可以移动不超过 $d$ 个单位距离。

你的初始位置是任意的（初始时刻为 $1$），求你通过移动能获取到的最大的开心值。

输入格式

第一行输入三个空格隔开的整数 $n,m,d$

$1\leq n\leq 150000,1\leq m\leq 300,1\leq d\leq n$

接下来 $m$ 行每行输入三个空格隔开的整数 $a_{i},b_{i},t_{i}$

$ 1\leq a_{i}\leq n,1\leq b_{i}\leq 10^{9},1\leq t_{i}\leq 10^{9} ,t_{i}\leq t_{i+1}$

输出格式

输出一个整数代表最大开心程度

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

-31

10 2 1
1 1000 4
9 1000 4

1992