#include<bits/stdc++.h>
using namespace std;
const int N=1010;
const long long MAX=1e18;
int c,T,n,m;
long long s;
long long k;
long long a[N][N];
long long f[N][N];
int main()
{
	scanf("%d%d",&c,&T);
	while(T--)
	{
		scanf("%d%d%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]);
		for(int i=1;i<=n;i++)
		for(int j=0;j<=m+1;j++)
		{
			f[i][j]=-MAX;
		}
		for(int j=1;j<=m;j++)
		{
			long long v=s+a[1][j];
			if(v<=0) continue;
			v=min(v,k);
			f[1][j]=v;
		}
		if(n>1)
		{
			for(int h=0;h<5;h++)
			{
				for(int j=1;j<=m;j++)
				{
					if(f[1][j-1]!=-MAX)
					{
						long long v=f[1][j-1]+a[1][j];
						if(v<0) continue;
						v=min(v,k);
						if(v>f[1][j]) f[1][j]=v;
					}
				}
				for(int j=m;j>=1;j--)
				{
					if(f[1][j+1]!=-MAX)
					{
						long long v=f[1][j+1]+a[1][j];
						if(v<0) continue;
						v=min(v,k);
						if(v>f[1][j]) f[1][j]=v;
					}
				}
			}
		}
		for(int i=2;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				if(f[i-1][j]!=-MAX) 
				{
				long long v=f[i-1][j]+a[i][j];
				if(v<0) continue;
				v=min(v,k);
				if(v>f[i][j]) f[i][j]=v;
				}
			}
			if(i!=n)
			{
			for(int h=0;h<5;h++)
			{
				for(int j=1;j<=m;j++)
				{
				if(f[i][j-1]!=-MAX)
				{
					long long v=f[i][j-1]+a[i][j];
					if(v<0) continue;
					v=min(v,k);
					if(v>f[i][j]) f[i][j]=v;
				}
				}
				for(int j=m;j>=1;j--)
				{
					if(f[i][j+1]!=-MAX)
					{
						long long v=f[i][j+1]+a[i][j];
						if(v<0) continue;
						v=min(v,k);
						if(v>f[i][j]) f[i][j]=v;
					}
				}
			}
			}
			if(i<n)
			{
				for(int j=1;j<=m;j++)
				{
					if(f[i][j]!=-MAX)
					{
						long long v=f[i][j]+a[i+1][j];
						if(v<0) continue;
						v=min(v,k);
						if(v>f[i+1][j])  f[i+1][j]=v;
					}
				}	
			}
		}
		long long ans=-1;
		for(int j=1;j<=m;j++)
		{
			if(f[n][j]>=0) ans=max(ans,f[n][j]);
		}
		printf("%lld\n",ans);
	}
	return 0;
}