#include <bits/stdc++.h>
#define int long long
using namespace std;
int dp[1005][1005],v[1005][1005],n,m,s,k;
inline long long read() {
    long long x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') { 
        if (ch == '-') f = -1; 
        ch = getchar(); 
    }
    while (ch >= '0' && ch <= '9') { 
        x = x * 10 + ch - '0'; 
        ch = getchar(); 
    }
    return x * f;
}
signed main1(){
    memset(dp,0xD0,sizeof dp);
    memset(v,0xD0,sizeof v);
    cin>>n>>m>>s>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            v[i][j]=read();
        }
    }
    for(int i=1;i<=n;i++){
        dp[1][i]=s+v[1][i];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(dp[i-1][j]>=0)dp[i][j]=max(dp[i][j],min(k,dp[i-1][j]+v[i][j]));
        }
        if(i==n)break;
        for(int j=1;j<=m;j++){
            if(v[i][j]+v[i][j+1]>0){
                if(v[i][j]>=0)v[i][j]=k;
                if(v[i][j+1]>=0)v[i][j+1]=k;
            }
        }
        for(int kt=0;kt<3;kt++){
            // cout<<i<<':'<<k<<' ';
            // for(int j=1;j<=m;j++){
            //     cout<<dp[i][j]<<' ';
            // }cout<<endl;
            for(int j=1;j<=m;j++){
                if(dp[i][j-1]>=0)dp[i][j]=max(dp[i][j],min(k,dp[i][j-1]+v[i][j]));
            }
            for(int j=m;j>=1;j--){
                if(dp[i][j+1]>=0)dp[i][j]=max(dp[i][j],min(k,dp[i][j+1]+v[i][j]));
            }
        }
    }
    int mx=INT_MIN;
    for(int i=1;i<=m;i++){
        mx=max(mx,dp[n][i]);
    }
    if(mx<0){
        cout<<-1<<endl;
    }else{
        cout<<mx<<endl;
    }
    return 0;
}
signed main(){
    int t;cin>>t>>t;
    while(t--)main1();
    return 0;
}