#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10;
int c,t,n,m,k,d;
int dis[N],b[N];
LL dp[N],tree[N],lazy_tag[N];
vector<pair<int,int>> p[N];
struct nb{
	int l,r,v;
}a[N];
inline int read(){
	int sum=0,fg=1;
	char ch=getchar();
	while(!(ch>='0'&&ch<='9')){
		if(ch=='-') fg=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		sum=(sum<<3)+(sum<<1)+(ch-'0');
		ch=getchar();
	}
	return sum*fg;
}
inline void print(LL x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9) print(x/10);
	putchar(x%10+'0'); 
}
inline void init(){
	int day,cnt,n2=0;
	for(int i=1;i<=m;i++){
		a[i].r=read(),a[i].l=a[i].r-read()+1,a[i].v=read();
		dis[(i<<1)-1]=a[i].l,dis[i<<1]=a[i].r;
	}
	sort(dis+1,dis+(m<<1)+1);
	for(int i=1;i<=(m<<1);i++) if(dis[i]!=dis[i-1]) b[++n2]=dis[i];
	n=n2;
	for(int i=1;i<=m;i++){
		a[i].l=lower_bound(b+1,b+n+1,a[i].l)-b;
		a[i].r=lower_bound(b+1,b+n+1,a[i].r)-b;
		p[a[i].r].push_back({a[i].l,a[i].v});
	}
}
inline void push_down(int x){
	tree[x<<1]+=lazy_tag[x];
	tree[(x<<1)+1]+=lazy_tag[x];
	lazy_tag[x<<1]+=lazy_tag[x];
	lazy_tag[(x<<1)+1]+=lazy_tag[x];
	lazy_tag[x]=0;
}
inline void insert(int x,int lf,int rt,int a,int b,int c){
	if(a<=lf&&rt<=b){
		tree[x]+=c;
		lazy_tag[x]+=c;
		return;
	}
	if(lazy_tag[x]) push_down(x);
	int mid=lf+rt>>1;
	if(a<=mid) insert(x<<1,lf,mid,a,b,c);
	if(b>mid) insert((x<<1)+1,mid+1,rt,a,b,c);
	tree[x]=max(tree[(x<<1)+1],tree[x<<1]);
}
inline LL query(int x,int lf,int rt,int a,int b){
	if(a>b) return 0;
	if(a<=lf&&rt<=b) return tree[x];
	if(lazy_tag[x]) push_down(x);
	int mid=lf+rt>>1;
	LL sum=-1e16;
	if(a<=mid) sum=max(sum,query(x<<1,lf,mid,a,b));
	if(b>mid) sum=max(sum,query((x<<1)+1,mid+1,rt,a,b));
	return sum;
}
inline int find(int x){
	int lf=1,rt=n,mid,ans;
	while(lf<=rt){
		mid=lf+rt>>1;
		if(b[mid]>=x) ans=mid,rt=mid-1;
		else lf=mid+1;
	}
	return ans;
} 
inline LL get_dp(int x){
	if(x>=0) return dp[x];
	return 0;
}
int main(){
	c=read(),t=read();
	while(t--){
		n=read(),m=read(),k=read(),d=read();
		init();
		for(int i=1;i<=n;i++){
			for(auto j:p[i]) insert(1,1,n,1,j.first,j.second);
			int j=find(b[i]-k+1);
			dp[i]=max(dp[i],query(1,1,n,j,i-1))-1ll*b[i]*d-1ll*d;
			int pos=i-2;
			if(b[i-1]!=b[i]-1) pos=i-1;
			dp[i]=max(dp[i],query(1,1,n,i,i)+get_dp(pos)-d);
			dp[i]=max(dp[i],dp[i-1]);
			insert(1,1,n,i,i,get_dp(pos)+1ll*b[i]*d);
		}
		print(dp[n]);
		putchar('\n');
		for(int i=1;i<=n;i++) p[i].clear();
		memset(tree,0,sizeof tree);
		memset(lazy_tag,0,sizeof lazy_tag);
		memset(dp,0,sizeof dp);
		memset(dis,0,sizeof dis);
		memset(b,0,sizeof b);
	}
	return 0;
}