借鉴 这篇题解 的思路，打了时间复杂度为 $O(n\log n)$ 的代码。样例2过不去，而且多测里第一组就挂了，不是没清空的问题。请大佬帮忙看看qwq。

Code：

/*
f[i]为前i天且强制第i天跑步的最大值，设gi = max{fj|1<=j<=i}
fi = max{g(j-1)-(i-j)*d+sum{vp|[lp,rp] in [j+1,i]}|i-k<=j<=i-1}

线段树维护 h(j) = g(j-1) + j*d + sum{vp|[lp,rp] in [j+1,i]};
表示第j天不跑，从j+1到i天都跑能得到的总贡献

线段树维护 max {h(j)} i-k<=j<=i-1
其中
（1） j*d这一项可以在建树时初始化。
（2） sum{...}这一项可以对每个rp=i进行区间加。
（3） g(j-1)这一项可以对每个j进行单点加
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5e5+5;
const LL INF=1e12;
int C,T,n,m,k;
LL d;
vector<int> Q[N];
struct Challenge{int l,r;LL x;} b[N];
LL f[N],ans;

struct Tree{int l,r; LL mx,A;} tr[N*4];
void brush(int u,LL A)
{
	tr[u].A+=A;
	tr[u].mx+=A;
}
void pushdown(int u)
{
	if(tr[u].l==tr[u].r || tr[u].A==0) return;
	brush(u*2,tr[u].A);
	brush(u*2+1,tr[u].A);
	tr[u].A=0;
}
void pushup(int u){tr[u].mx=max(tr[u*2].mx,tr[u*2+1].mx);}
void build(int u,int l,int r)
{
	tr[u]={l,r,0,0};
	if(l==r){tr[u].mx=l*d;return;} // （1）
	int mid=(l+r)/2;
	build(u*2,l,mid);
	build(u*2+1,mid+1,r);
	pushup(u);
}
void add(int u,int l,int r,LL A)
{
	pushdown(u);
	if(tr[u].l>r||tr[u].r<l) return;
	if(tr[u].l>=l && tr[u].r<=r){brush(u,A);return;}
	add(u*2,l,r,A);
	add(u*2+1,l,r,A);
	pushup(u);
}
LL query(int u,int l,int r)
{
	pushdown(u);
	if(tr[u].l>r||tr[u].r<l) return -INF;
	if(tr[u].l>=l&&tr[u].r<=r) return tr[u].mx;
	return max(query(u*2,l,r),query(u*2+1,l,r));
}

void solve_n()
{
	ans=-INF;
	build(1,0,n);
	for(int i=1;i<=n;++i) Q[i].clear();
	for(int i=1;i<=m;++i)
		Q[b[i].r].push_back(i); //根据r进行分离
	for(int i=1;i<=n;++i)
	{
		for(int& id:Q[i])
			add(1,0,b[id].l-1,b[id].x); //更新所有r=i的挑战（2）
		f[i]=query(1,max(i-k,0),i-1)-i*d; //求f[i]
		ans=max(ans,f[i]);
		add(1,i+1,i+1,ans); // （3）
		// cout << f[i] << "\n";
	}
	cout << ans << "\n";
}
signed main()
{
	// freopen("run2.in","r",stdin);
	// freopen("P9871.out","w",stdout);
	cin>>C>>T;
	while(T--)
	{
		ans=-INF;
		cin>>n>>m>>k>>d;
		for(int i=1;i<=m;++i)
		{
			int x,y; cin>>x>>y;
			b[i].l=x-y+1;
			b[i].r=x;
			cin>>b[i].x;
		}
		solve_n();
	}
	return 0;
}