#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,m,k,d;
int f[N],x[N],y[N],v[N],ha[N];
map<int,int> go;
vector<int> points,final,rs[N];

struct node {
	int l,r,maxn,lz;
	#define l(x) tr[x].l
	#define r(x) tr[x].r
	#define maxn(x) tr[x].maxn
	#define lz(x) tr[x].lz
};

struct segment {
	node tr[N*4];
	void pu(int x) {
		maxn(x)=max(maxn(x*2),maxn(x*2+1));
	}
	void pd(int x) {
		if(lz(x)) {
			maxn(x*2)+=lz(x);maxn(x*2+1)+=lz(x);
			lz(x*2)+=lz(x);
			lz(x*2+1)+=lz(x);
			lz(x)=0;
		}
	}
	void build(int x,int l,int r) {
		l(x)=l,r(x)=r;lz(x)=0;maxn(x)=0;
		if(l==r) {
			maxn(x)=0;
			return;
		}
		int mid=l+r>>1;build(x*2,l,mid);build(x*2+1,mid+1,r);pu(x);
		l(x)=l,r(x)=r;lz(x)=0;maxn(x)=0;
	}
	void change(int x,int ll,int rr,int k) {
		int l=l(x),r=r(x);
		if(l>=ll&&r<=rr) {
			maxn(x)+=k;
			lz(x)+=k;
			return; 
		}
		int mid=l+r>>1;
		pd(x);
		if(mid>=ll) change(x*2,ll,rr,k);
		if(mid<rr) change(x*2+1,ll,rr,k);
		pu(x); 
	}
	int qry(int x,int ll,int rr) {
		int l=l(x),r=r(x);
		if(l>=ll&&r<=rr) return maxn(x);
		int mid=l+r>>1,maxn=0;
		pd(x);
		if(mid>=ll) maxn=max(maxn,qry(x*2,ll,rr));
		if(mid<rr) maxn=max(maxn,qry(x*2+1,ll,rr));
		pu(x);
		return maxn;
	}
}tree;//线段树 
void init() {
	memset(tree.tr,0,sizeof tree.tr);
	for(int i=0;i<=2*m;i++) f[i]=x[i]=v[i]=y[i]=0;
	points.clear();final.clear();go.clear();
	for(int i=0;i<=2*m;i++) rs[i].clear(),ha[i]=0;
}
void in() {
	int top=0;
	scanf("%lld%lld%lld%lld",&n,&m,&k,&d);
	for(int i=1;i<=m;i++) {
		scanf("%lld%lld%lld",&x[i],&y[i],&v[i]);
		int tmp=x[i];
		x[i]=x[i]-y[i]+1;
		y[i]=tmp;
		if(y[i]<1) continue;
		points.push_back(x[i]);
		points.push_back(y[i]);
		if(!go[y[i]]) go[y[i]]=++top;
		rs[go[y[i]]].push_back(i); 
//		rs[y[i]].insert(i);
	}
}
int real(int x) {
	if(x>0) return f[x];
	return 0;
}
int find(int x) {
	int l=0,r=final.size()-1;
	while(l<r) {
		int mid=l+r>>1;
		if(final[mid]>=x) r=mid;
		else l=mid+1;
	}
	return r+1;
}
signed main() {
//	freopen("run4.in","r",stdin);
	int cc,tt;
	cin>>cc>>tt;
	while(tt--) {
		init();in();
		sort(points.begin(),points.end());
		for(int i=0;i<points.size();i++) {
			if(!i||points[i]!=points[i-1]) final.push_back(points[i]);
		}
		for(int i=0;i<final.size();i++) {
			//cout<<final[i]<<' ';
			ha[i+1]=final[i];
		}
		//cout<<endl;
		tree.build(1,1,final.size());
		for(int i=1;i<=final.size();i++) {
			int pl=ha[i];
			for(auto iter:rs[go[pl]]) tree.change(1,1,(lower_bound(final.begin(),final.end(),x[iter])-final.begin()+1),v[iter]);
			int la=find(pl-k+1);
			//cout<<"!!"<<la<<' '<<pl-k+1<<endl;
			f[i]=tree.qry(1,la,i-1)-d*ha[i]-d;
			int pos=i-2;
			if(ha[i]-ha[i-1]!=1) pos=i-1;
			f[i]=max(f[i],tree.qry(1,i,i)-d+real(pos));
			f[i]=max(f[i],real(i-1));
			tree.change(1,i,i,real(pos)+ha[i]*d);
			//cout<<f[i]<<' '<<ha[i]<<endl;
		}
		cout<<f[final.size()]<<endl;
	}
	return 0;
}