考场上大样例也没过，前面的数字对了，后面几个就输出-1。前面早早做完了（T1 70懂的都懂），然后这个调了1个半小时。。。调不出来只能先交了。。。然后65pts。。。

#include<bits/stdc++.h>
#define int long long 
using namespace std;
inline void cin__(int &n){
	int s=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		s=(s<<1)+(s<<3)+(ch^48);
		ch=getchar();
	}
	n=s*f;
}
inline void cout__(int n){
	if(n<0){
		putchar('-');
		n*=-1;
	}
	if(n>=10) cout__(n/10);
	putchar(n%10^48);
}
int T;
int inf=3e17;
int n,m,s,k;
int a[2005][2005];
int fl[2005][2005]; 
int fr[2005][2005];
int fu[2005][2005];
void solve(){
	cin__(n),cin__(m),cin__(s),cin__(k);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cin__(a[i][j]);
			a[i][j]=min(a[i][j],k);
		}
		for(int j=1;j<=m;++j){
			if(i<n&&j>1&&a[i][j]>=0&&a[i][j]+a[i][j-1]>0) a[i][j]=k;
			if(i<n&&j<m&&a[i][j]>=0&&a[i][j]+a[i][j+1]>0) a[i][j]=k;
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=0;j<=m+1;++j) fl[i][j]=fr[i][j]=fu[i][j]=-inf;
	}
	for(int j=1;j<=m;++j) fl[0][j]=fr[0][j]=fu[0][j]=s;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(fu[i-1][j]>=0) fu[i][j]=max(fu[i][j],min(fu[i-1][j]+a[i][j],k));
			if(fl[i-1][j]>=0) fu[i][j]=max(fu[i][j],min(fl[i-1][j]+a[i][j],k));
			if(fr[i-1][j]>=0) fu[i][j]=max(fu[i][j],min(fr[i-1][j]+a[i][j],k));
		}
		for(int j=1;j<=m;++j){
			if(fl[i][j-1]>=0) fl[i][j]=max(fl[i][j],min(fl[i][j-1]+a[i][j],k));
			if(fu[i][j-1]>=0) fl[i][j]=max(fl[i][j],min(fu[i][j-1]+a[i][j],k));
		}
		for(int j=m;j>=1;--j){
			if(fr[i][j+1]>=0) fr[i][j]=max(fr[i][j],min(fr[i][j+1]+a[i][j],k));
			if(fu[i][j+1]>=0) fr[i][j]=max(fr[i][j],min(fu[i][j+1]+a[i][j],k));
		}
	}
	int ans=-1;
//	for(int i=1;i<=n;++i){
//		for(int j=1;j<=m;++j){
//			cout<<fu[i][j]<<";"<<fl[i][j]<<";"<<fr[i][j]<<" ";
//		}
//		cout<<"\n";
//	}
	for(int j=1;j<=m;++j){
		ans=max(ans,fu[n][j]);
	}
	cout__(ans);
	putchar('\n');
}
signed main(){
//	freopen("journey4.in","r",stdin);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int c;
	cin__(c),cin__(T);
	while(T--) solve();
	return 0;
}