CF372C.Watching Fireworks is Fun

A festival will be held in a town's main street. There are n sections in the main street. The sections are numbered 1 through n from left to right. The distance between each adjacent sections is 1.

In the festival m fireworks will be launched. The i-th (1 ≤ i ≤ m) launching is on time t__i at section a__i. If you are at section x (1 ≤ x ≤ n) at the time of i-th launching, you'll gain happiness value b__i - |a__i - x| (note that the happiness value might be a negative value).

You can move up to d length units in a unit time interval, but it's prohibited to go out of the main street. Also you can be in an arbitrary section at initial time moment (time equals to 1), and want to maximize the sum of happiness that can be gained from watching fireworks. Find the maximum total happiness.

Note that two or more fireworks can be launched at the same time.

一场节日庆典将在小镇的主街上举行。主街分为 $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 \leq x \leq n$）。初始时刻（时间为 $1$）你可以位于任意区段，并希望最大化观看所有烟花所获得的总快乐值。请计算所能获得的最大总快乐值。

注意：可能有两次或更多次烟花在同一时刻燃放。

The first line contains three integers n, m, d (1 ≤ n ≤ 150000; 1 ≤ m ≤ 300; 1 ≤ d ≤ n).

Each of the next m lines contains integers a__i, b__i, t__i (1 ≤ a__i ≤ n; 1 ≤ b__i ≤ 109; 1 ≤ t__i ≤ 109). The i-th line contains description of the i-th launching.

It is guaranteed that the condition t__i ≤ t__i + 1 (1 ≤ i < m) will be satisfied.

第一行包含三个整数 $n$、$m$、$d$（$1 \le n \le 150000$；$1 \le m \le 300$；$1 \le d \le n$）。

接下来的 $m$ 行，每行包含三个整数 $a_i$、$b_i$、$t_i$（$1 \le a_i \le n$；$1 \le b_i \le 10^9$；$1 \le t_i \le 10^9$）。第 $i$ 行描述第 $i$ 次发射。

保证满足条件 $t_i \le t_{i+1}$（$1 \le i < m$）。

Print a single integer — the maximum sum of happiness that you can gain from watching all the fireworks.

Please, do not write the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.

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

请注意，在 C++ 中不要使用 %lld 说明符来读取或写入 64 位整数。推荐使用 cin、cout 流，或 %I64d 说明符。