#include<bits/stdc++.h>
using namespace std;
const int N = 4e3+10;
int n,m,k,x,y,v,t;
int a[N][N],dp[2][N],q[N];
int main(){
	cin>>n>>m>>k>>t;
	for(int i=1;i<=k;i++){
		cin>>x>>y>>v;
		a[x][y]=v;
	}
	int head=1,tail=0;
	for(int i=1;i<=m;i++) dp[1][i]=a[1][i];
	for(int i=2;i<=n;i++){
		for(int j=1;j<=t;j++){
			while(head<=tail&&dp[(i-1)&1][j]>dp[(i-1)&1][q[tail]]) tail--;
			q[++tail]=j;
		}//先将前t个放入单调队列 
		for(int j=1;j<=m;j++){
			if(j+t<=m){
				while(head<=tail&&dp[(i-1)&1][j+t]>dp[(i-1)&1][q[tail]]) tail--;
				q[++tail]=j+t;
				while(q[head]<j-t) head++;
			}
			dp[i&1][j]=dp[(i-1)&1][q[head]]+a[i][j];
		}
		head=1,tail=0;
	}
	int ans=0;
	for(int i=1;i<=m;i++) ans=max(ans,dp[n&1][i]);
	cout<<ans;
	return 0;
}

用了滚动数组