#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second

#define bzq "!!! tiaojiao"
 
const int N=200010;

int maxn[N<<2],lazy[N<<2];

int c,t,n,m,k,d,li[3*N],id,a[3*N],uid,dp[N];

vector<pii> f1[N];

int ls(int p){
	return p<<1;
}

int rs(int p){
	return p<<1|1;
}

int get2(int p){
	if(p>=0) return dp[p];
	return 0;
}

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

void push2(int p,int k){
	lazy[p]+=k;
	maxn[p]+=k;
}

void push1(int p){
	push2(ls(p),lazy[p]);
	push2(rs(p),lazy[p]);
	lazy[p]=0;
}

void get1(int p){
	maxn[p]=max(maxn[ls(p)],maxn[rs(p)]);
}

void ins(int p,int l,int r,int l1,int r1,int k){
	if(l>=l1&&r1>=r){
		push2(p,k);
		return ; 
	}
	push1(p);
	int mid=(l+r)>>1;
	if(l1<=mid&&r1>=l)ins(ls(p),l,mid,l1,r1,k);
	if(r1>mid&&l1<=r)ins(rs(p),mid+1,r,l1,r1,k); 
	get1(p);
}

int up(int p,int l,int r,int l1,int r1){
	if(l1>r1)return 0;
	if(l>=l1&&r1>=r)
		return maxn[p];
	push1(p);
	int mid=(l+r)>>1;
	if(l1<=mid)return up(ls(p),l,mid,l1,r1);
	if(r1>mid) return up(rs(p),mid+1,r,l1,r1);
	return max(up(ls(p),l,mid,l1,r1),up(rs(p),mid+1,r,l1,r1));
}

struct jcd{
	int x,y,v,id;
}f[N];

int find1(int k){
	int l=1,r=uid,ans=0;
	while(l<=r){
		int mid=(l+r)>>1;
		if(a[mid]>=k)r=mid-1,ans=mid;
		else l=mid+1;
	}
	return ans;
} 

signed main(){
//	freopen("1.out","w",stdout);
	cin>>c>>t;
	while(t--){
		id=uid=0;
		cin>>n>>m>>k>>d;
		for(int i=1;i<=m;i++){
			cin>>f[i].x>>f[i].y>>f[i].v;
			f[i].y=f[i].x-f[i].y+1;
			swap(f[i].x,f[i].y);
			li[++id]=f[i].x;li[++id]=f[i].y;
		}
		li[id+1]=0;
		sort(li+1,li+1+id);
		for(int i=2;i<=id+1;i++){
//			cout<<li[i-1]<<" ";
		if(li[i]!=li[i-1])
		a[++uid]=li[i-1];
//		cout<<a[uid]<<" ";
		}
//		cout<<endl;
//		cout<<bzq;
		build(1,1,uid);
//		cout<<"wyq"<<endl;
		for(int i=0;i<=uid;i++){
			dp[i]=0;
		}
		for(int i=1;i<=m;i++){
			f[i].x=lower_bound(a+1,a+uid+1,f[i].x)-a;
			f[i].y=lower_bound(a+1,a+uid+1,f[i].y)-a;
			f1[f[i].y].pb({f[i].x,f[i].v});
		//	cout<<f[i].x<<" "<<f[i].y<<endl;
		}
//		for(int i=1;i<=uid;i++){
//			cout<<a[i]<<" ";
//		}
	//	cout<<bzq<<endl;
		for(int i=1;i<=uid;i++){
			for(pii op:f1[i]){
			ins(1,1,uid,1,op.fi,op.se);
		//	cout<<bzq<<endl;
			}
			int j=find1(a[i]-k+1);
		//	cout<<j<<" ";
		//	cout<<"wyq1"<<endl;
			dp[i]=max(dp[i],up(1,1,uid,j,i-1))-1ll*a[i]*d-1ll*d;
			int j1=i-2;
			if(a[i-1]!=a[i]-1)j1=i-1;
//			cout<<dp[i]<<" ";
//			cout<<j<<" ";
			dp[i]=max(dp[i],up(1,1,uid,i,i)+get2(j1)-d);
//			cout<<up(1,1,uid,i,i)<<endl;
			dp[i]=max(dp[i],dp[i-1]);
		//	cout<<"pp"<<endl;
			ins(1,1,uid,i,i,get2(j1)+a[i]*d);
		}
	//	for(int i=1;i<=uid;i++)
	//	cout<<dp[i]<<" ";
	//	cout<<endl;
		cout<<dp[uid]<<endl;
		for(int i=1;i<=uid;i++)
		f1[i].clear();
	}
	return 0;
}