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

#include<bits/stdc++.h>
using namespace std;
int c,T,n,m,s,k,a[1005][1005],dp[1005];
int pd(int x){
	if(x<0)
		return -1;
	else if(x>k)
		return k;
	else
		return x;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>c>>T;
	while(T--){
		cin>>n>>m>>s>>k;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				cin>>a[i][j];
		for(int i=1;i<=n;i++)
			dp[i]=s;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++)
				if(dp[j]>=0)
                    dp[j]=pd(dp[j]+a[i][j]);
            if(i==n)
                break;
			priority_queue<pair<int,int>>q;
            int maxx=-1e9;
			for(int j=1;j<=m;j++)
				maxx=max(maxx,a[i][j]);
			if(maxx<0)
				break;
			for(int j=1;j<=m;j++)
				if(dp[j]>=0)
					q.push({dp[j],j});
			while(q.size()){
				auto d=q.top();
				q.pop();
				int z=d.first,u=d.second;
				if(dp[u]>z)continue;
				vector<int>dy={u-1,u+1};
				for(auto v:dy){
					if(v<1||v>m)continue;
					if(a[i][u]+a[i][v]>0){
						int h=pd(k+a[i][v]);
						if(dp[v]<h){
							dp[v]=h;
							q.push({dp[v],v});
						}
					}
					else if(pd(a[i][v]+dp[u])>dp[v]){
						dp[v]=pd(a[i][v]+dp[u]);
						q.push({dp[v],v});
					}
				}
			}
		}
        int maxx=-1;
		for(int i=1;i<=m;i++)
			maxx=max(maxx,dp[i]);
		cout<<maxx<<endl;
	}
	return 0;
}