#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2e5+5;
struct{
	LL w,lazy;
}tree[N<<2];
int ans,b[N],num,n,m,k,d,lsh[N],c,t;
LL dp[N];
struct{
	int l,r,k;
}a[N];
vector<pair<int,int> >q[N];
int read(){
	int x=1,c=0;
	int ch=getchar();
	while(ch<48||ch>57){
		if(ch='-') x=!x;
		ch=getchar();
	} 
	while(ch>=48&&ch<=57){
		c=(c<<1)+(c<<3)+(ch^48);
		ch=getchar();
	} 
	return x*c;
}

void add(int x,LL k){
	tree[x].w+=k,tree[x].lazy+=k;
}

void down(int x){
	add(x<<1,tree[x].lazy),add((x<<1)+1,tree[x].lazy);
	tree[x].lazy=0;
}

void modify(int x,int l,int r,int ll,int rr,LL k){
	if(ll<=l && r<=rr){
		add(x,k);
		return; 
	} 
	down(x);
	int mid=(l+r)>>1;
	if(ll<=mid && rr>=l) modify(x<<1,l,mid,ll,rr,k);
	if(rr>mid && ll<=r) modify((x<<1)|1,mid+1,r,ll,rr,k);
	tree[x].w=max(tree[x<<1].w,tree[(x<<1)|1].w);
}

int find(int x){
	int l=1,r=num;ans=num;
	while(l<=r){
		int mid=(l+r)>>1;
		if(b[mid]>=x) r=mid-1,ans=mid;
		else l=mid+1;
	}
	return ans;
}
void build(int x,int l,int r){
	tree[x]={0,0};
    int mid=(l+r)>>1;
	if(l==r)return;
	build(x<<1,l,mid),build((x<<1)|1,mid+1,r);
}
//1 1 3 2 2
LL line(int x,int l,int r,int ll,int rr){
	if(ll>rr) return 0;
	if(ll<=l&&r<=rr) return tree[x].w;
	down(x);
	int mid=(l+r)>>1;
	if(rr<=mid) return line(x<<1,l,mid,ll,rr);
	if(ll>mid) return line((x<<1)|1,mid+1,r,ll,rr);
	return max(line(x<<1,l,mid,ll,rr),line((x<<1)|1,mid+1,r,ll,rr));
}
int zheng(int x){
    if(x<0) return 0; 
    else return dp[x];
}
void work(){
    build(1,1,num);
	for(int i=0;i<=num;i++)  dp[i]=0;
	for(int i=1;i<=m;i++){
		a[i].l=lower_bound(b+1,b+num+1,a[i].l)-b;
		a[i].r=lower_bound(b+1,b+num+1,a[i].r)-b;
		q[a[i].r].push_back({a[i].l,a[i].k});
	}
//	for(int i=1;i<=m;i++) cout<<a[i].l<<" ";
//	cout<<endl;
//	for(int i=1;i<=m;i++) cout<<a[i].r<<" ";
	for(int i=1;i<=num;i++){
//		cout<<i<<endl;
//b[i] 1 2 3
		for(auto y:q[i])
		modify(1,1,num,1,y.first,y.second);
		int j=find(b[i]-k+1);
		//cout<<j<<endl;
		dp[i]=max(dp[i],line(1,1,num,j,i-1)-1ll*b[i]*d-1ll*d);
//		cout<<i<<endl; 
		int last=i-2;
		if(b[i-1]!=b[i]-1) last=i-1;
		dp[i]=max(dp[i-1],max(dp[i],line(1,1,num,i,i)+zheng(last)-d));
		modify(1,1,num,i,i,zheng(last)+1ll*b[i]*d);
//		cout<<i<<endl;
	}
	cout<<dp[num]<<endl;//我要疯了，调了好久 
	for(int i=1;i<=num;i++)q[i].clear();
} 


 
void pre(){
	n=read(),m=read(),k=read(),d=read();
	for(int i=1;i<=m;i++){
		a[i].r=read(),a[i].l=a[i].r-read()+1,a[i].k=read();
		lsh[(i<<1)-1]=a[i].l,lsh[(i<<1)]=a[i].r;
	}
	sort(lsh+1,lsh+2*m+1);
	num=0;
	lsh[2*m+1]=0;
	for(int i=2;i<=2*m+1;i++)if(lsh[i]!=lsh[i-1]) b[++num]=lsh[i-1];
    
}

int main(){	
	c=read(),t=read();
	while(t--){
		pre();
		work();
	}  
	for(int i=1;i<=num;i++) cout<<dp[i]<<endl; 
//	cout<<num;
	return 0; 
}