← 返回题目列表

Codeforces · 372/C

C. 看烟花很有趣

中文机器翻译题面 查看原题

城镇的主要街道将举行节日。主要街道有n段。这些部分从左到右编号为 1 到 n。每个相邻部分之间的距离为1。

节日期间将燃放烟花。第 i (1 ≤ i ≤ m) 次发射是在 ai 段的时间 ti 进行的。如果您在第 i 次启动时处于 x (1 ≤ x ≤ n) 部分,您将获得幸福值 bi - |ai - x| (请注意,幸福值可能是负值)。

单位时间间隔内最多可以移动d个长度单位,但禁止走出主街道。您也可以在初始时刻(时间等于1)处于任意部分,并希望最大化观看烟花所获得的快乐总和。找到最大的总幸福感。

请注意,可以同时发射两个或多个烟花。

输入

第一行包含三个整数 n、m、d (1 ≤ n ≤ 150000;1 ≤ m ≤ 300;1 ≤ d ≤ n)。

接下来的 m 行中的每一行都包含整数 ai、bi、ti (1 ≤ ai ≤ n; 1 ≤ bi ≤ 109; 1 ≤ ti ≤ 109)。第 i 行包含第 i 次启动的描述。

保证满足条件 ti ≤ ti + 1 (1 ≤ i < m)。

输出

打印一个整数——观看所有烟花可以获得的最大幸福感。

请不要编写 %lld 说明符来在 C++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

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

输出 #1

-31

输入 #2

10 2 1
1 1000 4
9 1000 4

输出 #2

1992