题目描述

一个节日将在城镇的主街道上举行。主街道被划分为 $n$ 个区域，这些区域从左到右依次编号为 $1$ 到 $n$。相邻区域之间的距离为 $1$ 单位长度。

节日期间将发射 $m$ 个烟花。第 $i$ 次（$1 \leq i \leq m$）发射将在时间 $t_{i}$ 于区域 $a_{i}$ 进行。如果你在第 $i$ 次发射时位于区域 $x$（$1 \leq x \leq n$），你将获得幸福值 $b_{i} - |a_{i} - x|$（注意幸福值可能为负数）。

你可以在单位时间间隔内移动最多 $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}$）。第 $i$ 行描述第 $i$ 次发射的信息。

保证满足 $t_{i} \leq t_{i+1}$（$1 \leq i \lt m$）的条件。

输出格式

输出一个整数——观看所有烟花所能获得的最大幸福值总和。

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

-31

10 2 1
1 1000 4
9 1000 4

1992