rt，$36$ 分解法，每个点除了第一组数据以外全部 WA

#include<bits/stdc++.h>
using namespace std;
long long c,t,n,m,k,d,tmp,tps,ans;
long long lim[1106],dp[1106][1106];//第i天连续泡了j天时的最大体力值 
struct node{
	long long x,y,v;
}a[114514];
bool cmp(node u,node v){
	if(u.x!=v.x)return u.x<v.x;
	else return u.y<v.y;
}
int main(){
	freopen("run2.in","r",stdin);
	scanf("%lld %lld",&c,&t);
	while(t--){
		ans=0xC0C0C0C0C0C0C0C0;
		tmp=1;
		tps=0; 
		memset(dp,192,sizeof(dp));
		scanf("%lld %lld %lld %lld",&n,&m,&k,&d);
		for(long long i=1;i<=m;i++)scanf("%lld %lld %lld",&a[i].x,&a[i].y,&a[i].v);
		sort(a+1,a+m+1,cmp);
		dp[0][0]=0;
		for(long long i=1;i<=n;i++){
			dp[i][0]=dp[i-1][0]; 
			lim[i]=min(k,i);
			tps=0;
			for(long long ii=1;ii<=lim[i];ii++){
				dp[i][ii]=max(dp[i][ii],dp[i-1][ii-1]-d);
				if(ii<=lim[i-1])dp[i][0]=max(dp[i][0],dp[i-1][ii]);
				if(a[tmp].x==i)if(a[tmp].y==ii){
					tps+=a[tmp].v;
					tmp++;
				}
				dp[i][ii]+=tps;
			}
		}
		for(long long i=0;i<=k;i++)ans=max(ans,dp[n][i]);
		printf("%lld\n",ans);
	}
	return 0;
}