rt，悬关
代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
int c, t, n, m, s, k, a[1010][1010], dp[1010][1010], S[1010][1010], d[1010][1010], p[1010][1010];
set<int> st;
signed main(){
	scanf("%lld%lld", &c, &t);
	while (t--){
		memset(d, 0, sizeof(d));
		memset(p, 0, sizeof(p));
		scanf("%lld%lld%lld%lld", &n, &m, &s, &k);
		for (int i=1; i<=n; i++){
			for (int j=1; j<=m; j++){
				scanf("%lld", &a[i][j]);
				S[i][j] = S[i][j-1] + a[i][j];
			}
		}
		for (int i=1; i<=m; i++)
			dp[0][i] = min(s, k);
		for (int i=1; i<=n; i++){
			d[i][m+1] = -1e18;
			for (int j=m; j>=1; j--){
				d[i][j] = max(d[i][j+1], dp[i-1][j])+a[i][j];
				if (d[i][j] < 0)
					d[i][j] = -1e18;
				if (d[i][j] > k)
					d[i][j] = k;
			}
			p[i][0] = -1e18;
			for (int j=1; j<=m; j++){
				p[i][j] = max(p[i][j-1], dp[i-1][j])+a[i][j];
				if (p[i][j] < 0)
					p[i][j] = -1e18;
				if (p[i][j] > k)
					p[i][j] = k;
			}
			for (int j=1; j<=m; j++){
				dp[i][j] = max(d[i][j], p[i][j]);
				if (dp[i][j] < 0)
					dp[i][j] = -1e18;
				if (dp[i][j] > k)
					dp[i][j] = k;
			}
			st.clear();
			for (int l=m; l>=1; l--){
				int o=dp[i][l];
				if (st.upper_bound(S[i][l-1]) != st.end())
					dp[i][l] = min(k, k+a[i][l]);
				if (dp[i][l] < 0)
					dp[i][l] = -1e18;
				if (o >= 0)
					st.insert(S[i][l]);
			}
			st.clear();
			for (int r=1; r<=m; r++){
				int o=dp[i][r];
				if (st.lower_bound(S[i][r]) != st.begin())
					dp[i][r] = min(k, k+a[i][r]);
				if (dp[i][r] < 0)
					dp[i][r] = -1e18;
				if (o >= 0)
					st.insert(S[i][r-1]);
			}
		}
		int ans=-1;
		for (int i=1; i<=m; i++)
			ans = max(ans, dp[n][i]);
		printf("%lld\n", ans);
	}
}