题目描述

一个节日将在城镇的主街道上举行。主街道被划分为 $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$）的条件。

输出格式

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

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

-31

10 2 1
1 1000 4
9 1000 4

1992