题解

#include<bits/stdc++.h>
#define ll long long
#define mid (l+r>>1)
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define e(x) for(int i=h[x],y=to[i];i;i=nxt[i],y=to[i])
#define Pi pair<int,int>
#define pb push_back
#define ui unsigned ll
inline int read(){int s=0,w=1;char c=getchar();while(c<48||c>57){if(c=='-')w=-1;c=getchar();}while(c>=48&&c<=57)s=(s<<1)+(s<<3)+c-'0',c=getchar();return s*w;}
const int N=2e5+5,M=1e6+5,inf=(1LL<<31)-1;
const ll llf=1e18; 
using namespace std;
int n,m,k,d,lsh[N],b[N],ln,testid,T;//days,tasks,limits,costs
struct node{
	int l,r,k;
}a[N];
inline void init(){
	ln=0;
	n=read(),m=read(),k=read(),d=read();
	lsh[m*2+1]=0;
	rep(i,1,m){
		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+m*2+1);
	rep(i,2,m*2+1)if(lsh[i]^lsh[i-1])b[++ln]=lsh[i-1];//离散化
}
ll dp[N];
inline ll got(int x){
	if(x>=0)return dp[x];
	return 0;
} 
vector<Pi >p[N];
#define E(x) for(auto y:p[x])
#define L x<<1
#define R L|1
#define lc L,l,mid
#define rc R,mid+1,r
#define OK Ll<=l&&r<=Rr
struct seg{
	ll w,laz;
}xd[N<<2];
inline void insert(int x,ll k){
	xd[x].w+=k,xd[x].laz+=k;
}
inline void pushdown(int x){
	insert(L,xd[x].laz),insert(R,xd[x].laz),xd[x].laz=0;
}
inline void getup(int x){
	xd[x].w=max(xd[L].w,xd[R].w);
}
inline void build(int x,int l,int r){
	xd[x]={0,0};
	if(l==r)return;
	build(lc),build(rc);
}
inline void modify(int x,int l,int r,int Ll,int Rr,ll k){
	if(OK)return insert(x,k),void();
	pushdown(x);
	if(Ll<=mid&&Rr>=l)modify(lc,Ll,Rr,k);
	if(Ll<=r&&Rr>mid)modify(rc,Ll,Rr,k);
	getup(x);
}
inline ll query(int x,int l,int r,int Ll,int Rr){
	if(Ll>Rr)return 0;
	if(OK)return xd[x].w;
	pushdown(x);
	if(Rr<=mid)return query(lc,Ll,Rr);
	if(Ll>mid)return query(rc,Ll,Rr);
	return max(query(lc,Ll,Rr),query(rc,Ll,Rr));
}
//线段树
#define Root 1,1,ln
inline int find(int x){
	int l=1,r=ln,ans=r;
	while(l<=r)if(b[mid]>=x)ans=mid,r=mid-1;
	else l=mid+1;
	return ans;
}//手写二分
inline void subtaskall(){
	build(Root);
	rep(i,0,ln)dp[i]=0;
	rep(i,1,m){
		a[i].l=lower_bound(b+1,b+ln+1,a[i].l)-b;
		a[i].r=lower_bound(b+1,b+ln+1,a[i].r)-b;
		p[a[i].r].pb({a[i].l,a[i].k});
	}
	rep(i,1,ln){
		E(i)modify(Root,1,y.first,y.second);
		int j=find(b[i]-k+1);
		dp[i]=max(dp[i],query(Root,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(Root,i,i)+got(pos)-d);
		dp[i]=max(dp[i],dp[i-1]);
		modify(Root,i,i,got(pos)+1LL*b[i]*d);
	}
	cout <<dp[ln]<<'\n';
	rep(i,1,ln)p[i].clear();
}//dp
inline void solve(){
	subtaskall();
}
int main(void){
	testid=read(),T=read();
	while(T--){
		init();
		solve();
	}
	return 0;
}