RT.

大样例都是有的对有的不对，目前觉得很大可能是线段树处理上的问题。

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define F first
#define S second
using namespace std;
typedef long long LL;
const int N=6e5+5,INF=1e18;

int _,T;

int n,m,k,d;
int a[N],tot;
int l[N],r[N],val[N];
vector<PII> vec[N];

struct LCT{
	int l,r;
	int sum,laz,max;
	LCT(){
		l=r=0;
		sum=laz=0;
		max=-INF;
	}
	void color(int val){
		sum+=val*(r-l+1);
		if(max==-INF) max=val;
		else max+=val;
		laz+=val;
	}
}t[N<<2];

void pushup(int p){
	t[p].sum=(t[p<<1].sum+t[p<<1|1].sum);
	t[p].max=max(t[p<<1].max,t[p<<1|1].max);
}

void pushdown(int p){
	if(t[p].laz){
		t[p<<1].color(t[p].laz);
		t[p<<1|1].color(t[p].laz);
		t[p].laz=0;
	}
}

void build(int p,int l,int r){
	t[p].l=l; t[p].r=r; t[p].laz=0;
	if(l==r){
		t[p].laz=t[p].sum=0;
		t[p].max=-INF;
		return;	
	}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	pushup(p);
}

void add(int p,int l,int r,int val){
	if(l<=t[p].l && t[p].r<=r){
		t[p].color(val);
		return;
	}
	pushdown(p);
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid) add(p<<1,l,r,val);
	if(r>mid) add(p<<1|1,l,r,val);
	pushup(p);
}

int getmax(int p,int l,int r){
	if(l<=t[p].l && t[p].r<=r) return t[p].max;
	pushdown(p);
	int mid=(t[p].l+t[p].r)>>1, ans=-INF;
	if(l<=mid) ans=max(ans,getmax(p<<1,l,r));
	if(r>mid) ans=max(ans,getmax(p<<1|1,l,r));
	return ans;
}

void Clear(){
	for(int i=1;i<=tot;i++) vec[i].clear();
	tot=0;
}

void INit(){
	scanf("%lld%lld%lld%lld",&n,&m,&k,&d);
	for(int i=1;i<=m;i++){
		scanf("%lld%lld%lld",&l[i],&r[i],&val[i]);
		l[i]=l[i]-r[i]+1; r[i]=l[i]+r[i]-1;
		a[++tot]=l[i]-1; a[++tot]=r[i]+1;
	}
	sort(a+1,a+tot+1);
	tot=unique(a+1,a+tot+1)-a-1;
	for(int i=1;i<=m;i++){
		int id=lower_bound(a+1,a+tot+1,r[i]+1)-a;
		vec[id].push_back({l[i],val[i]});
	}	
}

int f[N];
void Calc(){
	build(1,1,tot);
	int ans=0;
	add(1,1,1,f[1]=d*a[1]);
	for(int i=2;i<=tot;i++){
		for(auto j:vec[i]){
			int L=j.F, V=j.S;
//			cout<<"Money: "<<L<<" "<<a[i]-1<<" "<<V<<"  ";
			int id=lower_bound(a+1,a+tot+1,L)-a-1;
//			cout<<id<<"\n";
			add(1,1,id,V);
		}
//		cout<<i<<":  \n";
		int lid=lower_bound(a+1,a+tot+1,a[i]-k-1)-a, rid=lower_bound(a+1,a+tot+1,a[i]-1)-a; 
//		cout<<"id: "<<lid<<" "<<rid<<"\n";
		f[i]=getmax(1,lid,rid)+d-d*a[i];
//		cout<<a[i]<<" "<<getmax(1,lid,rid)<<" "<<f[i]<<"\n";
		add(1,i,i,f[i]+a[i]*d);
		ans=max(ans,f[i]);
//		cout<<"\n";
	}
	printf("%lld\n",ans);
}

signed main(){
//	freopen("run2.in","r",stdin);
//	freopen("qwq.out","w",stdout);
	
	scanf("%lld%lld",&_,&T);
	while(T--){
		Clear(); // 多测要清空 
		INit();
		Calc();
	}
	return 0;
}