【例题4】燃放烟火

题目描述

一个城镇有$n$个烟火点，从左到右编号为$1$~$n$，每个烟火点之间距离$1$个单位长度。节日中有$m$个烟火要放，给定放的地点$a_{i}$，时间$t_{i}$，如果点燃第$i$个烟花时你在烟火点$x$，你可以获得$b_{i} - |a_{i} - x|$的开心值。

你每个单位时间可以移动不超过$d$个单位距离。你的初始位置是任意的（初始时刻为$1$），求你通过移动能获取到的最大的开心值。

输入格式

第一行包含三个整数$n$，$m$，$d$。

接下来的$m$行，每行包含三个整数$a_{i}$，$t_{i}$，$b_{i}$。

输出格式

打印一个整数：你可以从观看所有烟花中获得的最大幸福总和。

数据范围与提示

对于$100\%$的数据：

• $1 < n < 150000$
• $1 < m < 300$
• $1 \leq d \leq n$
• $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