#include <bits/stdc++.h>
#define int long long
using namespace std;
int dp[1005][1005],v[1005][1005],n,m,s,k;
signed main1(){
    cin>>n>>m>>s>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>v[i][j];
            dp[i][j]=LONG_LONG_MIN;
        }
    }
    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 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++){
                dp[i][j]=max(dp[i][j],min(k,dp[i][j-1]+v[i][j]));
            }
            for(int j=m;j>=1;j--){
                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;
}