跑的超级慢，本地大样例8s，洛谷评测机56pts

#include<bits/stdc++.h>
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
using namespace std;
const ll N=1000010,INF=1e9+7,INFF=0x3f3f3f3f3f3f3f3f;
inline ll max(ll x,ll y){return x>y?x:y;}
inline ll min(ll x,ll y){return x<y?x:y;}
inline void swap(ll &x,ll &y){x^=y^=x^=y;}
ll c,t,n,m,k,d,tot,ans,cnt;
vector<ll> s;
vector<pair<ll,ll> > h[N];
unordered_map<ll,ll> ls,rs;
inline ll read(){
    char c=getchar();ll x=0,f=1;
    while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}
    while('0'<=c&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
struct SegmentTree{
	ll l,r;
	ll dat,tag;
	#define l(x) tree[x].l
	#define r(x) tree[x].r
	#define dat(x) tree[x].dat
	#define tag(x) tree[x].tag
}tree[N<<3];
void pushup(ll p){
	dat(p)=max(dat(l(p)),dat(r(p)));
}
ll build(){
	ll p=++cnt;
	l(p)=r(p)=0;
	dat(p)=tag(p)=0;
	return p;
}
void pushdown(ll p){
	if(!tag(p))return;
	if(l(p))dat(l(p))+=tag(p),tag(l(p))+=tag(p);
	if(r(p))dat(r(p))+=tag(p),tag(r(p))+=tag(p);
	tag(p)=0;
}
void insert(ll p,ll l,ll r,ll pos,ll val){
	if(l==r){dat(p)+=val;return;}
	ll mid=(l+r)>>1;
	pushdown(p);
	if(pos<=mid){
		if(!l(p))l(p)=build();
		insert(l(p),l,mid,pos,val);
	}
	else{
		if(!r(p))r(p)=build();
		insert(r(p),mid+1,r,pos,val);
	}
	pushup(p);
}
void change(ll p,ll l,ll r,ll L,ll R,ll val){
	if(L>R)return;
	if(L<=l&&r<=R){
		dat(p)+=val;tag(p)+=val;
		return;
	}
	ll mid=(l+r)>>1;
	pushdown(p);
	if(L<=mid&&l(p))change(l(p),l,mid,L,R,val);
	if(R>mid&&r(p))change(r(p),mid+1,r,L,R,val);
	pushup(p);
}
ll query(ll p,ll l,ll r,ll L,ll R){
	if(L>R)return -INFF;
	if(L<=l&&r<=R)return dat(p);
	ll mid=(l+r)>>1,val=-INFF;
	pushdown(p);
	if(L<=mid&&l(p))val=max(val,query(l(p),l,mid,L,R));
	if(R>mid&&r(p))val=max(val,query(r(p),mid+1,r,L,R));
	return val;
}
void add(int x){
	if(x<=0)return;
	if(!rs[x])rs[x]=++tot,s.push_back(x);
}
int main(){
	c=read();t=read();
	while(t--){
		ans=cnt=tot=0;dat(0)=-INFF;
		s.clear();ls.clear();rs.clear();
		n=read();m=read();k=read();d=read();
		for(ll i=1;i<=m;i++){
			ll x=read(),y=read(),v=read();
			if(y<=k){
				ls[x-y+1]=1;
				add(x-1);add(x);add(x+1);
				add(x-y);add(x-y+1);add(x-y+2);
				h[rs[x]].push_back(make_pair(x-y+1,v));
			}
		}
		build();
		insert(1,0,n,0,-d*n);
		sort(s.begin(),s.end());
		for(ll i=0;i<(ll)s.size();i++){
			ll r=s[i],lst=ans;
			insert(1,0,n,r,-d*(n-r));
			for(pair<ll,ll> z:h[rs[r]])
				change(1,0,n,0,z.fi-1,z.se);
			ans=max(ans,query(1,0,n,max(0,r-k),r-1)+d*(n-r));
			insert(1,0,n,r,ls[r+1]?lst:ans);
		}
		printf("%lld\n",ans);
		for(int i=1;i<=tot;i++)h[i].clear();
	}
	return 0;
}