目前大样例 5 用时 5s，应该不是代码写挂了。

#include <bits/stdc++.h>
#define int long long
#define For(i, a, b) for (int i = (a); i <= (b); i ++)
#define foR(i, a, b) for (int i = (a); i >= (b); i --)
using namespace std;
int n, m, k, d, mx;
int cnt, b[800005], dp[800005];
int mxx[2400005], tag[2400005];
vector <int> v[800005];
struct chall {int x, y, d, len;}a[100005];
bool cmp (chall c1, chall c2) {return c1.y < c2.y;}
inline int read () {
	char ch = getchar ();
	int x = 0;
	while (ch < '0' || ch > '9') ch = getchar ();
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + ch - 48;
		ch = getchar ();
	}
	return x;
}
void pushdown (int l, int r, int k) {
	if (tag[k]) {
		mxx[k << 1] += tag[k];
		mxx[k << 1 | 1] += tag[k];
		tag[k << 1] += tag[k];
		tag[k << 1 | 1] += tag[k];
		tag[k] = 0;
	}
}
inline void update (int l, int r, int k, int x, int y, int v) {
	if (x > y) return;
	if (x <= l && y >= r) {
		mxx[k] += v;
		tag[k] += v;
		return;
	}
	pushdown (l, r, k);
	int mid = l + r >> 1;
	if (x <= mid) update (l, mid, k << 1, x, y, v);
	if (y > mid) update (mid + 1, r, k << 1 | 1, x, y, v);
	mxx[k] = max (mxx[k << 1], mxx[k << 1 | 1]);
}
inline int query (int l, int r, int k, int x, int y) {
	if (x > y) return 0;
	if (x <= l && y >= r) return mxx[k];
	pushdown (l, r, k);
	int mid = l + r >> 1, res = -1000000000000000000;
	if (x <= mid) res = query (l, mid, k << 1, x, y);
	if (y > mid) res = max (res, query (mid + 1, r, k << 1 | 1, x, y) );
	return res;
}
void solve () {
	n = read ();
	m = read ();
	k = read ();
	d = read ();
	For (i, 1, m) {
		a[i].y = read ();
		a[i].len = read ();
		a[i].d = read ();
		a[i].x = a[i].y - a[i].len + 1;
		b[++ cnt] = a[i].y; if (a[i].y != 1) b[++ cnt] = a[i].y - 1; b[++ cnt] = a[i].y + 1;
		b[++ cnt] = a[i].x; if (a[i].x != 1) b[++ cnt] = a[i].x - 1; b[++ cnt] = a[i].x + 1;
	}
	sort (b + 1, b + cnt + 1);
	cnt = unique (b + 1, b + cnt + 1) - b;
	For (i, 1, m) {
		a[i].x = lower_bound (b + 1, b + cnt + 1, a[i].x) - b;
		a[i].y = lower_bound (b + 1, b + cnt + 1, a[i].y) - b;
		mx = max (mx, a[i].y);
	}
	sort (a + 1, a + m + 1, cmp);
	For (i, 1, m) v[a[i].y].push_back (i);
	For (i, 1, mx) update (1, mx, 1, i, i, b[i] * d);
	int sum = 0;
	//第 j 个位置存储 b[j] - query (j - 1)
	//其中 query(j) 指 sum (j...n)，则修改 i 时，query (1...i + 1) 都要做修改 
	For (i, 1, mx) {
		dp[i] = dp[i - 1];
		if (v[i].empty () ) {
			if (i + 2 <= mx) update (1, mx, 1, i + 2, i + 2, dp[i]);
			continue;
		}
		For (j, 0, v[i].size () - 1) {
			update (1, mx, 1, a[v[i][j] ].x + 1, mx, -a[v[i][j] ].d);
			sum += a[v[i][j] ].d;
		}
		int j = i;
		foR (l, 17, 0) if (j > (1 << l) && b[i] - b[j - (1 << l)] + 1 <= k) j -= 1 << l;
		dp[i] = max (dp[i], sum - b[i] * d - d + query (1, mx, 1, j, i) );
		if (i + 2 <= mx) update (1, mx, 1, i + 2, i + 2, dp[i]);
//		for (int j = i + 1; j >= 2 && b[i] - b[j + 1] + 1 <= k; j --) {
//			dp[i] = max (dp[i], (j >= 2 ? dp[j - 2] : 0) + sum - b[i] * d - d - query (j - 1) + b[j] * d);
//		}
	}
	cout << dp[mx];
	n = m = k = d = cnt = 0;
	For (i, 1, 800000) b[i] = dp[i] = 0;
	For (i, 1, 4 * mx) mxx[i] = tag[i] = 0;
	For (i, 1, mx) v[i].clear ();
}
signed main () {
	int _ = 1;
	cin >> _ >> _;
	while (_ --) {
		solve ();
		cout << '\n';
	}
	return 0;
}