#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
const int MAXN = 1005;
int a[MAXN][MAXN];
int dp[MAXN];
bool check(int n, int m, int s, int k) {
    for (int j = 0; j <= m; j++) {
        dp[j] = -INF;
    }
    for (int j = 1; j <= m; j++) {
        int val = s + a[1][j];
        if (val < 0) continue;
        if (val > k) val = k;
        dp[j] = val;
    }
    bool ok = 0;
    for (int j = 1; j <= m; j++) {
        if (dp[j] != -INF) {
            ok = 1;
            break;
        }
    }
    if (!ok) return 0;
    for (int i = 1; i < n; i++) {
        int curr[MAXN];
        memcpy(curr, dp, sizeof(dp));
        bool f;
        do {
            f = 0;
            for (int j = 2; j <= m; j++) {
                if (curr[j - 1] == -INF) continue;
                int val = curr[j - 1] + a[i][j];
                if (val < 0) continue;
                if (val > k) val = k;
                if (val > curr[j]) {
                    curr[j] = val;
                    f = 1;
                }
            }
            for (int j = m - 1; j >= 1; j--) {
                if (curr[j + 1] == -INF) continue;
                int val = curr[j + 1] + a[i][j];
                if (val < 0) continue;
                if (val > k) val = k;
                if (val > curr[j]) {
                    curr[j] = val;
                    f = 1;
                }
            }
        } while (f);
        for (int j = 1; j <= m; j++) {
            if (curr[j] == -INF) {
                dp[j] = -INF;
                continue;
            }
            int val = curr[j] + a[i + 1][j];
            if (val < 0) {
                dp[j] = -INF;
            } else {
                if (val > k) val = k;
                dp[j] = val;
            }
        }
        ok = 0;
        for (int j = 1; j <= m; j++) {
            if (dp[j] != -INF) {
                ok = 1;
                break;
            }
        }
        if (!ok) break;
    }
    return ok;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int c, T;
    cin >> c >> T;
    while (T--) {
        int n, m, s, k;
        cin >> n >> m >> s >> k;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> a[i][j];
            }
        }
        bool ok = check(n, m, s, k);
        if (!ok) {
            cout << -1 << '\n';
        } else {
            int maxx = -1;
            for (int j = 1; j <= m; j++) {
                if (dp[j] > maxx) {
                    maxx = dp[j];
                }
            }
            cout << maxx << '\n';
        }
    }
    return 0;
}