NOIPT4疑似宇宙射线36->0

//[Data Removed] [Data Removed] qinianji [Data Removed]
#include<bits/stdc++.h>
using namespace std;
struct kill{
	int x,y,v;
}a[100006];
int n,m,k,d,c,t;
long long dp[1005][1006],f[1005],get[1005][1005];
long long mmax(long long a,long long b){
	if(a>b)    return a;
	return b; 
}
long long mmin(long long a,long long b){
	if(a<b)    return a;
	return b; 
}
bool cmp(kill aa,kill bb){
	if(aa.x==bb.x)    return aa.y<bb.y;
	return aa.x<bb.x;
}
int main(){
    freopen("run.in","r",stdin);
	freopen("run.out","w",stdout);
	cin >> c >> t;
	if(c<=9){
	    while(t--){
		    cin >> n >> m >> k >> d;
		    for(int i=1;i<=m;i++){
			    scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].v);
			}
			sort(a+1,a+m+1,cmp);
			int cnt=1;
			for(int i=1;i<=n;i++){
				for(int j=1;j<=mmin(k,i);j++){
					get[i][j]=get[i][j-1]+get[i-1][j-1]-(j!=1?get[i-1][j-2]:0);
					while(cnt<=m){
						if(a[cnt].x!=i)    break;
						if(a[cnt].y!=j)    break;
						get[i][j]+=a[cnt].v;
						cnt++;
					}
				}
			}
		    for(int i=1;i<=n;i++){
		        f[i]=-1e18;
		        for(int j=0;j<=mmin(k,i);j++){
		        	if(j==0){
		        		dp[i][j]=f[i-1];
					}
		        	else if(j==i || j==i-1){
		        		dp[i][j]=get[i][j]-j*d;
					}
					else{
						dp[i][j]=get[i][j]-j*d+f[i-j-1];
					}
					f[i]=mmax(dp[i][j],f[i]);
				}
		    }
		    cout<<f[n]<<endl;
	    }
    }
	return 0;	
}