#include <vector>
#include <math.h>
#include <stdio.h>
#include <ctype.h>
#include <algorithm>
#define N 100001
#define int long long
using namespace std;

int read(){
	int ans = 0;
	char ch = getchar();
	while(!isdigit(ch)){
		ch = getchar();
	}
	while(isdigit(ch)){
		ans *= 10;
		ans += ch ^ 48;
		ch = getchar();
	}
	return ans;
}
void write(int n){
	if(n > 9) write(n / 10);
	putchar(48 ^ n % 10);
}

int _, n, m, k, d, lsh[N << 1], cnt;
struct op{
	int x, y, val;
}a[N];

struct segtree{//存 dp[i] + i*d 的最大值
	#define lc rt << 1
	#define rc rt << 1 | 1

	struct node{
		int val, laz;
	}node[N << 4];

	void pushup(int rt){
		node[rt].val = max(node[lc].val, node[rc].val);
	}

	void pushdown(int rt){
		if(node[rt].laz){
			node[lc].laz += node[rt].laz;
			node[rc].laz += node[rt].laz;
			node[lc].val += node[rt].laz;
			node[rc].val += node[rt].laz;
			node[rt].laz = 0;
		}
	}

	void build(int rt, int l, int r){
		node[rt].val = 0;
		node[rt].laz = 0;
		if(l == r){
			return;
		}
		int mid = (l + r) >> 1;
		build(lc, l, mid);
		build(rc, mid + 1, r);
	}

	void update(int rt, int l, int r, int L, int R, int k){
		if(l >= L && r <= R){
			node[rt].laz += k;
			node[rt].val += k;
			return;
		}
		if(r < L || l > R){
			return;
		}
		int mid = (l + r) >> 1;
		pushdown(rt);
		update(lc, l, mid, L, R, k);
		update(rc, mid + 1, r, L, R, k);
		pushup(rt);
	}

	int query(int rt, int l, int r, int L, int R){
		if(l >= L && r <= R){
			return node[rt].val;
		}
		if(r < L || l > R){
			return 0;
		}
		int mid = (l + r) >> 1;
		pushdown(rt);
		return max(query(lc, l, mid, L, R), query(rc, mid + 1, r, L, R));
	}

	#undef lc
	#undef rc
}tree;

/*
dp[i] = dp[j] + f(j + 1, i - 1) - (i - j - 1) * d
0 <= i - j - 1 <= k
*/

signed main(){
	freopen("run1.in", "r", stdin);
	freopen("run.out", "w", stdout);

	read();
	_ = read();
	int x, y;
	while(_--){
		cnt = 0;
		n = read(), m = read(), k = read(), d = read();
		for(int i = 1; i <= m; i++){
			x = read(), y = read();
			a[i].x = x - y + 1;
			a[i].y = x;
			a[i].val = read();
			lsh[++cnt] = a[i].x - 1;
			lsh[++cnt] = a[i].y + 1;
		}
		sort(lsh + 1, lsh + cnt + 1);
		cnt = unique(lsh + 1, lsh + cnt + 1) - lsh - 1;
		for(int i = 1; i <= m; i++){
			a[i].x = lower_bound(lsh + 1, lsh + cnt + 1, a[i].x - 1) - lsh;
			a[i].y = lower_bound(lsh + 1, lsh + cnt + 1, a[i].y + 1) - lsh;
		}

		vector<int> seg[N << 1];//存终点为 i 的线段编号有哪些，相当于桶
		for(int i = 1; i <= m; i++){
			seg[a[i].y].emplace_back(i);
		}
		tree.build(1, 1, cnt);
		tree.update(1, 1, cnt, 1, 1, lsh[1] * d);
		int ans = 0, p = 0/*表示符合 i - j - 1 <= k 的最前位置*/;
		for(int i = 2; i <= cnt; i++){
			//用到的时候再更新线段的贡献
			for(auto j : seg[i]){
				tree.update(1, 1, cnt, 1, a[j].y, a[j].val);
			}
			while(lsh[i] - lsh[p] - 1 > k){
				p++;
			}
			ans = max(ans, tree.query(1, 1, cnt, p, i - 1) - (lsh[i] - 1) * d);
			//更新 dp[i]
			tree.update(1, 1, cnt, i, i, ans + lsh[i] * d);
		}

		write(ans);
		putchar(10);
	}
	return 0;
}