P9871

才发现蓝题以下的基本都被菜就多练的我刷掉了
from 0pts to 100pts
所以，这道题就是线段树+dp喽

#include<bits/stdc++.h>
#define rep(k,l,r) for(long long k=l;k<=r;++k)
#define per(k,r,l) for(long long k=r;k>=l;--k)
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
namespace IO {
	char Is[(1<<21)+10],Os[(1<<21)+10];
	long long Ipt,Opt;
	inline char gc() {
		if(Ipt==1<<21)
			Ipt=0;
		if(!Ipt)
			Is[fread(Is,1,1<<21,stdin)]=0;
		return Is[Ipt++];
	}
	inline void flush() {
		fwrite(Os,1,Opt,stdout);
		Opt=0;
	}
	inline void pc(char x) {
		if(Opt==1<<21)
			flush();
		Os[Opt++]=x;
	}
	inline long long read() {
		long long x=0;
		char ch=gc();
		while(ch<'0'||ch>'9')
			ch=gc();
		while(ch<='9'&&ch>='0')
			x=x*10+ch-'0',ch=gc();
		return x;
	}
}
using IO::read;
struct SGT {
	struct node {
		long long l,r,val,tag;
	}; node tree[300005<<2];
	#define ls(k) (k<<1)
	#define rs(k) (k<<1|1)
	inline void push_up(long long k) {
		tree[k].val=max(tree[ls(k)].val,tree[rs(k)].val);
	}
	void build(long long k,long long l,long long r) {
		tree[k]={l,r,0ll,0ll};
		if(l==r)
			return;
		long long mid=(l+r)>>1;
		build(ls(k),l,mid);
		build(rs(k),mid+1,r);
		push_up(k);
	}
	inline void upd(long long k,long long val) {
		tree[k].val+=val; tree[k].tag+=val;
	}
	inline void push_down(long long k) {
		long long &t=tree[k].tag;
		if(t) {
			upd(ls(k),t); upd(rs(k),t);
			t=0;
		}
	}
	void update(long long k,long long ql,long long qr,long long val) {
		if(ql<=tree[k].l&&tree[k].r<=qr) {
			upd(k,val);
			return;
		}
		push_down(k);
		if(ql<=tree[ls(k)].r)
			update(ls(k),ql,qr,val);
		if(qr>=tree[rs(k)].l)
			update(rs(k),ql,qr,val);
		push_up(k);
	}
	long long query(long long k,long long ql,long long qr) {
		if(ql<=tree[k].l&&tree[k].r<=qr)
			return tree[k].val;
		push_down(k);
		long long res=-0x3f3f3f3f3f3f3f3f;
		if(ql<=tree[ls(k)].r)
			chkmax(res,query(ls(k),ql,qr));
		if(qr>=tree[rs(k)].l)
			chkmax(res,query(rs(k),ql,qr));
		return res;
	}
}; SGT T;
long long t[300005],len;
inline long long get_id(long long x) {
	return lower_bound(t+1,t+len+1,x)-t;
}
struct seg {
	long long l,r,val;
	bool operator < (const seg &tmp) const {
		return r<tmp.r;
	}
}; seg a[300005];
inline void solve() {
	long long n=read(),m=read(),k=read(),d=read();
	len=0;
	rep(i,1,m) {
		long long r=read(),x=read(),val=read();
		a[i]={r-x,r,val};
		t[++len]=a[i].l;
		t[++len]=a[i].r;
	}
	sort(t+1,t+len+1);
	len=unique(t+1,t+len+1)-t-1;
	T.build(1,0,len-1);
	rep(i,1,m) {
		a[i].l=get_id(a[i].l); 
		a[i].r=get_id(a[i].r);
	}
	sort(a+1,a+m+1);
	long long res=0,p=1;
	rep(i,1,len) {
		T.update(1,0,i-1,-d*(t[i]-t[i-1]));
		while(p<=m&&a[p].r==i)T.update(1,0,a[p].l,a[p].val),++p;
		chkmax(res,T.query(1,get_id(t[i]-k),i-1));
		if(i+1<len)T.update(1,i+1,i+1,res); 
	}
	printf("%lld\n",res);
}
signed main() {
	long long _=read(),testcase=read();
	while(testcase--)solve();
	return 0;
}