#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int c, t, n, m, k, x, y;

ll d, v[300005], dp[100005], ans;

int lsh[300005], lshlen; // 离散化 

vector <int> lt[300005]; // 右端点对应的编号

struct TREE{
	ll t, m;
	int l, r;
} tr[1200005]; // 线段树 

struct LMN{
	int l, r;
} dmn[100005]; // 区间左右区间 

void build(int p, int l, int r) {
	if (l == r) {
		tr[p] = {0, d * lsh[l], l, r};
		return;
	}
	tr[p] = {0, 0, l, r};
	int mid = (l + r) >> 1;
	build(p * 2, l, mid);
	build(p * 2 + 1, mid + 1, r);
	tr[p].m = max(tr[p * 2].m, tr[p * 2 + 1].m);
}
void pushdown(int p) {
	if (tr[p].l == tr[p].r) {
		tr[p].t = 0;
		return;
	}
	tr[p * 2].m += tr[p].t;
	tr[p * 2].t += tr[p].t;
	tr[p * 2 + 1].m += tr[p].t;
	tr[p * 2 + 1].t += tr[p].t;
	tr[p].t = 0;
}
ll query(int p, int l, int r) {
	if (tr[p].t) pushdown(p);
	if (tr[p].l > r || tr[p].r < l) return 0;
	if (tr[p].l >= l && tr[p].r <= r) return tr[p].m;
	return max(query(p * 2, l, r), query(p * 2 + 1, l, r));
}
void modify(int p, int l, int r, int v) {
	if (tr[p].t) pushdown(p);
	if (tr[p].l > r || tr[p].r < l) return;
	if (tr[p].l >= l && tr[p].r <= r) {
		tr[p].m += v;
		tr[p].t += v;
		return;
	}
	int mid = (tr[p].l + tr[p].r) >> 1;
	if (mid >= l) modify(p * 2, l, r, v);
	if (mid <= r) modify(p * 2 + 1, l, r, v);
	tr[p].m = max(tr[p * 2].m, tr[p * 2 + 1].m);
} 

void out() {
	for (int i = 1; i <= lshlen; i++){
		printf("%lld ", query(1, i, i));
	}
	cout << endl;
}

int main() {
	scanf("%d%d", &c, &t);
	while(t--) {
		scanf("%d%d%d%lld", &n, &m, &k, &d);
		
		memset(dp, 0, sizeof dp);
		lshlen = 0;
		ans = 0;
		
		for (int i = 1; i <= m; i++) {
			scanf("%d%d%lld", &dmn[i].r, &dmn[i].l, &v[i]);
			dmn[i].l = dmn[i].r - dmn[i].l + 1;
			lsh[++lshlen] = dmn[i].l;
			lsh[++lshlen] = dmn[i].r;
			lsh[++lshlen] = dmn[i].r - k + 1;
		}
		sort(lsh + 1, lsh + lshlen + 1);
		lshlen = unique(lsh + 1, lsh + lshlen + 1) - lsh - 1;
		for(int i = 1; i <= lshlen; i++) {
			lt[i].clear();
		}
		for (int i = 1; i <= m; i++) {
			dmn[i].l = lower_bound(lsh + 1, lsh + lshlen + 1, dmn[i].l) - lsh;
			dmn[i].r = lower_bound(lsh + 1, lsh + lshlen + 1, dmn[i].r) - lsh;
			lt[dmn[i].r].push_back(i);
		}
		build(1, 1, lshlen);
		for (int i = 1; i <= lshlen; i++) {
			if (!lt[i].empty()) for (int j = 0; j < lt[i].size(); j++) {
				modify(1, 1, dmn[lt[i][j]].l, v[lt[i][j]]);
			}
//			cout << "[]" << query(1, lower_bound(lsh + 1, lsh + lshlen + 1, lsh[i] - k + 1) - lsh, i) - d * (lsh[i] + 1) << endl;
			dp[i] = max(query(1, lower_bound(lsh + 1, lsh + lshlen + 1, lsh[i] - k + 1) - lsh, i) - d * (lsh[i] + 1), ans);
			int idx = lower_bound(lsh + 1, lsh + lshlen + 1, lsh[i] + 2) - lsh;
			if (lsh[idx] >= lsh[i] + 2) modify(1, idx, idx, dp[i]);
			ans = max(dp[i], ans);
		}
		printf("%lld\n", dp[lshlen]);
	}
	return 0;
}

写的线段树+离散化