城镇的主要街道将举行节日。主要街道有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