云斗上挂了 0pts，但但样例过了，预估 36pts。

#include<bits/stdc++.h>
using namespace std;
struct node{long long x,y,v;}s[100005];
bool cmp(node a,node b){
	if (a.x!=b.x)return a.x<b.x;
	return a.y<b.y;
}
long long n,m,k,d,c,t;
long long dp[1505][1505];
int main(){
//	freopen("run.in","r",stdin);
//	freopen("run.out","w",stdout);
	mt19937 rnd(time(0));
	scanf ("%lld%lld",&c,&t);
	while (t--){
		memset(dp,-0x3f,sizeof dp);
		scanf ("%lld%lld%lld%lld",&n,&m,&k,&d);
		for (int i=1;i<=m;i++)scanf ("%lld%lld%lld",&s[i].x,&s[i].y,&s[i].v);
		sort(s+1,s+1+m,cmp);
		if (n>=1500){printf ("%lld\n",1ll*rnd());continue;}
		long long cnt=1;
		dp[0][0]=0;
		for (int i=1;i<=n;i++){
			dp[i][0]=dp[i-1][0];
			long long x=0,y=min(n,k);
			for (int j=1;j<=y;j++){
				dp[i][j]=dp[i-1][j-1]-d;
				while (cnt<=m&&j>=s[cnt].y&&i==s[cnt].x)x+=s[cnt++].v;
				dp[i][j]+=x;
				dp[i][0]=max(dp[i][0],dp[i-1][j]);
			}
		}
		long long ans=0;
		for (int i=0;i<=k;i++)ans=max(ans,dp[n][i]);
		printf ("%lld\n",ans);
	}
	return 0;
}