题目描述
数轴上,有 1,2,…,n 总共 n 个点。
有 m 个事件,第 i 次发生在时间 ti,点 ai 上。
如果你在第 i 次事件发生时位于点 x,你将获得收益 bi−∣ai−x∣。
注意,m 次收益你都必须获得,即使它可能是负的。另外,ti 不保证互不相同。
你可以在单位时间间隔内,在数轴上移动最多 d 单位长度,但禁止移动到 [1,n] 的范围以外,你可以在初始时刻(时间等于 1 时)处于范围内的任意整数点上。
求按照最优的方式移动,能获得的最大总收益是多少。
输入格式
第一行包含三个整数 n,m,d。
接下来 m 行,每行包含三个整数 ai,bi,ti。
保证满足 ti≤ti+1。
输出格式
输出一个整数,表示最大的总收益。
样例 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
数据范围
对于所有测试数据,保证:1≤n≤150000,1≤m≤300,1≤d≤n,1≤ai≤n,1≤bi≤109,1≤ti≤109。
| 测试点 |
n≤ |
m≤ |
特殊性质 |
| 1∼4 |
10 |
5 |
无 |
| 5∼6 |
1000 |
100 |
tn≤100 |
| 7∼10 |
无 |
| 11∼12 |
50000 |
200 |
| 13∼14 |
150000 |
300 |
d=1,ti=i |
| 15∼20 |
无 |