Migrated from Lutece 2040 烟花是扁的还是圆的

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

子辉选在这天邀 Sakura 吃饭不是没有原因。今晚有盛大的烟花表演，趁着烟花表演的表白是最浪漫的。 子辉和 Sakura 所在的小镇有$n$个区域，从左到右$1$编号为$n$，每个区域之间距离$1$个单位距离。这一晚有 $m$ 个烟花要放，给定每个烟花释放的放的地点$a_i$、时间$t_i$ ,如果 子辉 和 Sakura 当时在区域 $x$ ，那么可以获得$b_i - | a_i - x |$的开心值。子辉 和 Sakura 每个单位时间可以移动不超过$d$个单位距离。他们的初始位置没有限制（初始时刻为1），求他们这一晚通过移动能获取到的最大的开心值。

看完烟花后，子辉拉起了Sakura的纤细的手，那些表白的话正准备说出。这时，Sakura先说了句 :“你说，烟花是扁的还是圆的呢？”。——未完待续

Input

第一行包含3个整数$n$, $m$, $d$ ($1≤n≤150000$; $1 \le m \le 300$; $1 \le d \le n$). 接下来$m$行，每行包含3个整数， $a_i$ , $b_i$ , $t_i$ ($1 \le a_i \le n$; $1 \le b_i \le10^9$; $1 \le t_i \le 10^9$） 输入保证$t_i≤t_{i+1}$ ($1≤i<m$)

Output

一个整数，表示最大开心值。

Samples

10 2 1
1 1000 4
9 1000 4

1992

Resources

2018 UESTC Training for Dynamic Programming