整道题是一个很典的分段DP模型：一眼区间拆成两个点：把值盖在左端点上，每个格子的费用转化成负贡献塞进贡献，右端点负责加贡献（扫到之后把贡献加到左端点对应位置）。

这样，设 $f_i$ 为强行走到位置 $i$ 的答案，有方程

$f_i=\max_{j\le i}^{i-j+1\le k}\{\max_{p\lt j}\{f_p\}+\sum_{q=j}^{i}a_q\}$，注意根据定义，前继必须和产生贡献的左端点断开至少一个位置。

设 $g_i=\max_{j\lt i}\{f_j\},s_i=\sum_{j=1}^{i}a_i$，方程转变为

$f_i=\max_{j\le i}^{i-j+1\le k}\{g_j+s_i-s_{j-1}\}$

把 $g_i-s_{i-1}$ 扔进线段树处理即可。对于 $n$ 过大的地方，离散化。

具体实现上为了更好写，可以把 $g_i$ 定义修改为 $\max_{j\le i}\{f_j\}$，这样的话和 $s_i$ 下标对齐， $g_i-s_i$ 更方便维护一点。

补充一些地方：

在最大化能量的情况下，在没有奖励区间覆盖的地方跑步是无意义的，不盖完一个区间的跑步也是没意义的，也就是说，一次跑步的终点一定是某个奖励区间右端点，起点一定是奖励区间左端点。

在这个背景下，扩展到 $n \le 10^9$ 时，考虑所有可能的转移点：区间左端点（作为前继），区间右端点（显然），区间右端点向前延申到最靠前的起始位置（方便处理查询边界），这样总值域可以被缩小到至多 $3m$ 级别。

具体实现上，每次切换位置前缀加若干个 $d$，加点也是前缀加，因为只要从比某个位置远的当前点转移到此处一定能够覆盖;可以直接把 $s_i$ 提前加到线段树上，这样转移直接求区间最大值就行。以及，注意下标偏移，差点写死我（笔者VP时光这题写了4个小时）。

代码在本OJ上会被卡常到44分，其他地方都能过。

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+11;
using ll=long long;
int t,n,k,m,d,q;
struct segtree
{
	int ls[N*2],rs[N*2],cnt,rt;
	ll mx[N*2],tag[N*2];
	void up(int x)
	{
		mx[x]=max(mx[ls[x]],mx[rs[x]]);
	}
	void down(int x)
	{
		if(!tag[x]) return;
		mx[ls[x]]+=tag[x],tag[ls[x]]+=tag[x];
		mx[rs[x]]+=tag[x],tag[rs[x]]+=tag[x];
		tag[x]=0;
	}
	void build(int &x,int l,int r)
	{
		if(!x) x=++cnt;int mid=(l+r)/2;
		if(l==r) return;
		build(ls[x],l,mid);build(rs[x],mid+1,r);up(x);
	}
	void add(int x,int l,int r,int sl,int sr,ll v)
	{
		if(sl<=l&&r<=sr) return mx[x]+=v,tag[x]+=v,void();
		int mid=(l+r)/2;down(x);
		if(sl<=mid) add(ls[x],l,mid,sl,sr,v);
		if(mid+1<=sr) add(rs[x],mid+1,r,sl,sr,v);up(x);
	}
	ll qmx(int x,int l,int r,int ql,int qr)
	{
		if(!x) return -1e18;
		if(ql<=l&&r<=qr) return mx[x];
		int mid=(l+r)/2;down(x);
		if(ql<=mid&&mid+1<=qr) return max(qmx(ls[x],l,mid,ql,qr),qmx(rs[x],mid+1,r,ql,qr));
		else if(mid+1<=qr) return qmx(rs[x],mid+1,r,ql,qr);
		return qmx(ls[x],l,mid,ql,qr);
	}
	void clear()
	{
		for(int i=0;i<=cnt;++i) ls[i]=rs[i]=mx[i]=tag[i]=0;
		cnt=0;rt=0;
	}
};
ll drc[N];int dix;
int qidx(int x)
{
	return lower_bound(drc+1,drc+dix+1,x)-drc;
}
struct segs
{
	int l,r;ll vl;
}a[N];
bool operator <(const segs &a,const segs &b)
{
	return a.r<b.r;
}
segtree st;
//g[i]=max_{j<=i}f[j]
//s[i]=\sum a[i]-d*i
//f[i]=max{g[j-2]+s[i]-s[j-1]}
//h(j,i)=h[j]=g[j-2]+s[i]-s[j-1]
//f[i]=max{h[j-1]},i-k<=j<=i
//
int mian()
{
	cin>>n>>m>>k>>d;
	for(int i=1;i<=m;++i)
	{
		cin>>a[i].r>>a[i].l>>a[i].vl;
		a[i].l=a[i].r-a[i].l;
		drc[++dix]=a[i].l,drc[++dix]=a[i].r-k,drc[++dix]=a[i].r;
	}
	sort(drc+1,drc+dix+1);dix=unique(drc+1,drc+1+dix)-drc-1;
	//for(int i=1;i<=dix;++i) aa[i]=-1ll*d*(drc[i]);
	st.build(st.rt,0,dix-1);
	for(int i=1;i<=m;++i) a[i].l=qidx(a[i].l),a[i].r=qidx(a[i].r);
	sort(a+1,a+m+1);
	ll ans=0;int ptr=1;
	for(int i=1;i<=dix;++i)
	{
		st.add(st.rt,0,dix-1,0,i-1,-1ll*d*(drc[i]-drc[i-1]));
		while(ptr<=m&&a[ptr].r<=i) 
			st.add(st.rt,0,dix-1,0,a[ptr].l,a[ptr].vl),++ptr;
		ans=max(ans,st.qmx(st.rt,0,dix-1,qidx(drc[i]-k),i-1));
		if(i+1<dix) st.add(st.rt,0,dix-1,i+1,i+1,ans);
	}
	cout<<ans<<'\n';
	st.clear();dix=0;
	return 0;
}
int main()
{
	//freopen("run.in","r",stdin);
	//freopen("run.out","w",stdout);
	cin>>q>>t;
	while(t--) mian();
	return 0;
}