题目描述
一个城镇有 $n$ 个烟火点，从左到右编号为 $1\sim 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$。
输出
打印一个整数：你可以从观看所有烟花中获得的最大幸福总和。
样例输入输出
输入#1
复制
50 3 1
49 1 1
26 1 4
6 1 10
提示
对于 $100\%$ 的数据，$1 \leq n \leq 150000$，$1 \leq m \leq 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}$。