#include<bits/stdc++.h>
using namespace std;
#define int long long
int id,T;
int N,m,k,d;
int dp[100005];
int point[600005];
vector<pair<int,int> > p[200005];
struct task{
	int l,r,k;
}a[200005];
int b[200005];
int cnt;
inline void init(){
	cnt=0;
	cin>>N>>m>>k>>d;
	point[2*m+1]=0;
	for(int i=1;i<=m;i++){
		cin>>a[i].r;
		int len;cin>>len;
		a[i].l=a[i].r-len+1;
	    cin>>a[i].k;
	    point[i*2]=a[i].r;
		point[i*2-1]=a[i].l;
	}
	sort(point+1,point+2*m+1);
	for(int i=2;i<=2*m+1;i++){
		if(point[i]^point[i-1]) b[++cnt]=point[i-1];
	}
}
struct node{
	int val,tag;
	int l,r,siz;
}t[800005];
#define ls x<<1
#define rs x<<1|1
inline int pushup(int x){
	t[x].val=max(t[ls].val,t[rs].val);
}
inline void build(int x,int l,int r){
	t[x].l=l,t[x].r=r,t[x].siz=r-l+1;
	t[x].val=t[x].tag=0;
	if(l==r) return;
	int mid=(l+r)/2;
	build(ls,l,mid);
	build(rs,mid+1,r);
}
inline void pushdown(int x){
     t[ls].val+=t[x].tag;
     t[rs].val+=t[x].tag;
     t[ls].tag+=t[x].tag;
     t[rs].tag+=t[x].tag;
     t[x].tag=0;
}
inline void add(int x,int ll,int rr,int k){
	if(t[x].l>rr||t[x].r<ll) return ;
	if(t[x].l>=ll&&t[x].r<=rr){
		t[x].val+=k;
		t[x].tag+=k;
		return;
	}
	pushdown(x);
	add(ls,ll,rr,k);
	add(rs,ll,rr,k);
	pushup(x);
}
inline int query(int x,int ll,int rr){
	if(t[x].l>rr||t[x].r<ll) return 0;
	if(t[x].l>=ll&&t[x].r<=rr) return t[x].val;
	pushdown(x);
	return max(query(ls,ll,rr),query(rs,ll,rr));
}
inline int findx(int x){
	int l=1,r=cnt;
	int ans=r;//
	while(l<=r){
		int mid=(l+r)/2;
		if(b[mid]>=x) ans=mid,r=mid-1;
		else l=mid+1;
	}
	return ans;
}
inline int got(int x){
	if(x>=0) return dp[x];
	return 0;
}
inline void solve(){
	//cout<<"///"<<endl;
	build(1,1,cnt);
	
	for(int i=0;i<=cnt;i++) dp[i]=0;
	
	for(int i=1;i<=m;i++){
		a[i].l=lower_bound(b+1,b+cnt+1,a[i].l)-b;
		a[i].r=lower_bound(b+1,b+cnt+1,a[i].r)-b;
		p[a[i].r].push_back({a[i].l,a[i].k});
	}
	for(int i=1;i<=cnt;i++){
		for(int q=0;q<p[i].size();q++)add(1,1,p[i][q].first,p[i][q].second);
		int j=findx(b[i]-k+1);
		dp[i]=max(dp[i],query(1,j,i-1))-b[i]*d-d;
		int pos=i-2;
		if(b[i-1]!=b[i]-1) pos=i-1;
		dp[i]=max(dp[i],got(pos)+query(1,i,i)-d);
		dp[i]=max(dp[i],dp[i-1]);
		add(1,i,i,got(pos)+b[i]*d);
	}
	cout<<dp[cnt]<<endl;
	for(int i=1;i<=cnt;i++) p[i].clear();
}
signed main(){
	//freopen("run6.in","r",stdin);
	//freopen("run.out","w",stdout);
	cin>>id>>T;
	while(T--){
		init();
		solve();
	}
	return 0;
}