样例没过qaq

#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define zb x*2
#define yb x*2+1
const int N=1e5+7;
struct Seg{
	int l,r;
	ll sum,tag,mx;
	#define l(x) st[x].l
	#define r(x) st[x].r
	#define mx(x) st[x].mx 
	#define sum(x) st[x].sum 
	#define tag(x) st[x].tag 
}st[4*N];
vector <int> vc[N];
void pushup(int x){
	mx(x)=max(mx(zb),mx(yb));
	sum(x)=sum(zb)+sum(yb);
}
void pushdown(int x){
	tag(zb)+=tag(x); tag(yb)+=tag(x);
	sum(zb)+=tag(x)*(r(zb)-l(zb)+1);
	sum(yb)+=tag(x)*(r(yb)-l(yb)+1);
	mx(zb)+=tag(x); mx(yb)+=tag(x);
	tag(x)=0;
}
void build(int x,int l,int r){
	l(x)=l;r(x)=r;
	if(l==r){
		return ;
	}
	int mid=(l+r)>>1;
	build(zb,l,mid);
	build(yb,mid+1,r);
}
void add(int x,int l,int r,ll w){
	if(l<=l(x)&&r(x)<=r){
		sum(x)+=w; mx(x)+=w;
		tag(x)+=w;
		return;
	}
	pushdown(x);
	int mid=(l(x)+r(x))>>1;
	if(l<=mid) add(zb,l,r,w);
	if(mid+1<=r) add(yb,l,r,w);
	pushup(x);
}
ll query(int x,int l,int r){//求max 
	if(l<=l(x)&&r(x)<=r){
		return mx(x);
	}
	pushdown(x);
	ll ans=0;
	int mid=(l(x)+r(x))>>1;
	if(l<=mid) ans=max(ans,query(zb,l,r));
	if(mid+1<=r) ans=max(ans,query(yb,l,r));
	return ans;
}

ll ld[N],rd[N],v[N],b[2*N];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int c,T;
	cin>>c>>T;
	while(T--){
		ll n,m,k,d;
		cin>>n>>m>>k>>d;
		memset(b,0,sizeof(b));
		memset(ld,0,sizeof(ld));memset(rd,0,sizeof(rd));
		int tot=0;
		for(int i=1;i<=N;i++)
			vc[i].clear();
		for(int i=1;i<=m;i++){
			int x,y;
			cin>>x>>y>>v[i];
			rd[i]=x;  ld[i]=x-y+1;
		
			b[++tot]=ld[i]-1; b[++tot]=rd[i]+1;//离散化 
		}
		int len=unique(b+1,b+1+tot)-b-1;
		for(int i=1;i<=m;i++){
			ld[i]=lower_bound(b+1,b+len+1,ld[i]-1)-b;
			rd[i]=lower_bound(b+1,b+len+1,rd[i]+1)-b;
			vc[rd[i]].push_back(i);
		}
		build(1,1,len);
		ll res=0,lim=0;
		for(int i=2;i<=len;i++){//len就是离散化后的n 
			for(int j=0;j<vc[i].size();j++){
				add(1,1,ld[vc[i][j]],v[vc[i][j]]);
			}
			while(b[i]-b[lim]-1>k) lim++;//k的限制 
			res=max(res,query(1,lim,i-1)-d*b[i]+d);
			if(i==len) cout<<res<<'\n';
			add(1,i,i,res+b[i]*d);
		}	
	}
	return 0;
}