#include <bits/stdc++.h>

#define int long long
#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)

using namespace std;

const int N = 2e6 + 10, mod = 1e9 + 7;

int c, T, n, m, k, d, b[N], cnt, f[N];
int mx[N];

struct Node {
	int x, y, v;
	bool operator < (const Node b) const {
		return y < b.y;
	}
};

Node a[N];

struct node {
	int l, r, maxn, m, add;
};

node t[4 * N];

void push_up (int p) {
	t[p].maxn = max(t[ls(p)].maxn, t[rs(p)].maxn);
	return;
}

void build (int l, int r, int p) {
	t[p].l = l, t[p].r = r, t[p].add = 0;
	if (l == r) {
		t[p].maxn = 0;
		return;
	}
	int mid = (l + r) >> 1;
	build (l, mid, ls(p));
	build (mid + 1, r, rs(p));
	push_up(p);
	return;
}

void lazy_tag (int p, int d) {
	t[p].maxn += d;
	t[p].add  += d;
	return;
}

void push_down (int p) {
	lazy_tag (ls(p), t[p].add);
	lazy_tag (rs(p), t[p].add);
	t[p].add = 0;
	return;
}

void update (int l, int r, int p, int d) {
	if (l <= t[p].l && t[p].r <= r) {
		lazy_tag (p, d);
		return;
	}
	push_down(p);
	int mid = (t[p].l + t[p].r) >> 1;
	if (l <= mid) update (l, r, ls(p), d);
	if (r >  mid) update (l, r, rs(p), d);
	push_up(p);
	return;
}

void modify (int l, int r, int p, int d) {
	if (l <= t[p].l && t[p].r <= r) {
		t[p].maxn = max(t[p].maxn, d);
		return;
	}
	push_down(p);
	int mid = (t[p].l + t[p].r) >> 1;
	if (l <= mid) modify (l, r, ls(p), d);
	if (r >  mid) modify (l, r, rs(p), d);
	push_up(p);
	return;
}

int query (int l, int r, int p) {
	if (l <= t[p].l && t[p].r <= r) {
		return t[p].maxn;
	}
	push_down(p);
	int mid = (t[p].l + t[p].r) >> 1, sum = 0;
	if (l <= mid) sum = max(sum, query (l, r, ls(p)));
	if (r >  mid) sum = max(sum, query (l, r, rs(p)));
	return sum;
}

vector <pair <int, int> > q[N];

signed main() {
    scanf("%lld%lld", &c, &T);
    while (T -- ) {
    	cnt = 0;
    	memset(mx, 0, sizeof(mx));
    	scanf("%lld%lld%lld%lld", &n, &m, &k, &d);
    	for (int i = 1; i <= m; ++ i ) {
    		scanf("%lld%lld%lld", &a[i].x, &a[i].y, &a[i].v);
			int tmp = a[i].x;
			a[i].x -= a[i].y - 1;
			a[i].y = tmp;
			b[ ++ cnt] = a[i].x, b[ ++ cnt] = a[i].y;
		}
    	sort(a + 1, a + m + 1);
    	sort(b + 1, b + cnt + 1);
    	cnt = unique (b + 1, b + cnt + 1) - b - 1;
    	build (1, cnt + 2, 1);
    	for (int i = 1; i <= cnt; ++ i ) q[i].clear();
    	for (int i = 1; i <= m; ++ i ) {
    		q[lower_bound(b + 1, b + cnt + 1, a[i].y) - b].push_back({lower_bound(b + 1, b + cnt + 1, a[i].x) - b, a[i].v});
    	//	cout << (lower_bound(b + 1, b + cnt + 1, a[i].x) - b) << ' ' << (lower_bound(b + 1, b + cnt + 1, a[i].y) - b) << endl;
		}
		int ans = 0;
		for (int i = 1; i <= cnt; ++ i ) {
			f[i] = f[i - 1];
			mx[i] = max(mx[i], mx[i - 1]);
			update (i, i, 1, mx[i]);
			update (1, i, 1, -d * (b[i] - b[i - 1]));
			for (pair <int, int> j : q[i]) {
				update (1, j.first, 1, j.second);
			}
			int at = lower_bound(b + 1, b + cnt + 1, b[i] - k + 1) - b;
//			cout << at << "\n";
			f[i] = max(f[i], query (at, i, 1));
			if (b[i] + 1 == b[i + 1]){
				mx[i + 2] = max(mx[i + 2], f[i]);
			}
			else mx[i + 1] = max(mx[i + 1], f[i]);
			ans = max(ans, f[i]);
//			cout << f[i] << endl;
		}
		printf("%lld\n", ans);
	}
	return 0;
}