rt, 第七个点一直 WA。

// 设 f[i, j] 表示 再放第 i 支烟花时，在第 j 个位置上获得的 最大快乐值
// f[i, j] = max (f[i - 1, k] + bi - |ai - j|)
// f[i][j] = max (f[i - 1, k]) + bi - |ai - j|  (k∈ (ti - t[i-1])[j-d, j+d])
#include <bits/stdc++.h>
 
using namespace std;
#define int long long

const int N = 2e6 + 5;

inline int fir(int a){ return a & 1; }
inline int sec(int a){ return a & 1 ^ 1; }
inline int kabs(int a){ return a >= 0? a: -a; }
inline int max(int a, int b){ return a > b? a: b; }

int n, m, d, len, ans = -0x7f7f7f7f7f7f7f7f, head, tail;
int a[N], b[N], t[N], Q[N], ma[N], f[2][N];

signed main(){
	//freopen("a.in", "r", stdin);
	//freopen("a.out", "w", stdout);
	scanf("%lld%lld%lld", &n, &m, &d);
	for(int i = 1; i <= m; i++) scanf("%lld%lld%lld", &a[i], &b[i], &t[i]);
	for(int i = 1; i <= n; i++) f[1][i] = b[1] - kabs(a[1] - i); 
	for(int i = 2; i <= m; i++){
		head = 1, tail = 0, len = (t[i] - t[i - 1]) * 2 * d + 1;
		if(d * (t[i] - t[i - 1]) > n){
			ma[1] = -0x7f7f7f7f7f7f7f7f;
			for(int j = 1; j <= n; j++) ma[1] = max(ma[1], f[sec(i)][j]);
			for(int j = 2; j <= n; j++) ma[j] = ma[j - 1];
			goto loop;
		}
		for(int j = 1; j <= n + (t[i] - t[i - 1]) * d; j++){
			while(head <= tail && f[sec(i)][Q[tail]] <= f[sec(i)][j]) tail--;
			Q[++tail] = j;
			while(Q[head] <= j - len && head <= tail) head++;
			if(j > (t[i] - t[i - 1]) * d) ma[j - (t[i] - t[i - 1]) * d] = f[sec(i)][Q[head]];
		}
		loop:
		for(int j = 1; j <= n; j++)
			f[fir(i)][j] = ma[j] + b[i] - kabs(a[i] - j);
//		for(int j = 1; j <= n; j++) printf("%d ", ma[j]);
//		cout << endl;
//		for(int j = 1; j <= n; j++)
//			printf("%d ", f[fir(i)][j]);
//		cout << endl;
	}
	for(int i = 1; i <= n; i++)
		ans = max(ans, f[fir(m)][i]);
	printf("%lld", ans);
	exit(0);