https://www.luogu.com.cn/record/198825873

#include <iostream>
#include <cstring>
#include <deque>
using namespace std;
int n, m, k, t;
int a[5010][5010];
struct f{
	int x, id;
};
int dp[5010][5010];
int main(){
	cin >> n >> m >> k >> t;
	for(int i = 1; i <= k; i++){
		int x, y, v;
		cin >> x >> y >> v;
		a[x][y] = v;
	}
	memset(dp, -0x3f3f3f3f, sizeof(dp));
	
	for(int i = 1; i <= m; i++){
		dp[1][i] = a[1][i];
	}
	deque<f> q;
	for(int i = 1; i <= 1 + t && i <= m; i++){
		while (!q.empty() && q.back().x < dp[1][i]) {
			q.pop_back();
		}
		q.push_back({dp[1][i], i});
	}
	for(int i = 2; i <= n; i++){
		for(int j = 1; j <= m; j++){
			dp[i][j] = max(dp[i][j], a[i][j] + q.front().x);
			if(j + t <= m){
				while (!q.empty() && q.back().x < dp[i - 1][j + t]) {
					q.pop_back();
				}
				q.push_back({dp[i - 1][j + t], j + t});
				
			}
			while (!q.empty() && q.front().id <= j - t) {
				q.pop_front();
			}
		}
		while (!q.empty()) {
			q.pop_front();
		}
		for(int j = 1; j <= 1 + t && j <= m; j++){
			while (!q.empty() && q.back().x < dp[i][j]){
				q.pop_back();
			}
			q.push_back({dp[i][j], j});
		}
	}
	int ans = -1e9 - 7;
	for(int i = 1; i <= m; i++){
		ans = max(ans, dp[n][i]);
	}
	cout << ans << endl;

	return 0;
}