#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int c, T;
    cin >> c >> T;
    
    while (T--) {
        int n, m;
        long long s, k;
        cin >> n >> m >> s >> k;
        
        vector<vector<long long>> a(n + 1, vector<long long>(m + 2, 0));
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                cin >> a[i][j];
            }
        }
        
        vector<vector<vector<long long>>> dp(n + 1, vector<vector<long long>>(m + 2, vector<long long>(2, -1)));
        
        // 初始化第一行
        for (int j = 1; j <= m; ++j) {
            long long initial = s + a[1][j];
            if (initial < 0) continue;
            initial = min(initial, k);
            dp[1][j][0] = initial;
            dp[1][j][1] = initial;
        }
        
        // 处理中间行
        for (int i = 1; i < n; ++i) {
            for (int j = 1; j <= m; ++j) {
                for (int dir = 0; dir < 2; ++dir) {
                    if (dp[i][j][dir] == -1) continue;
                    
                    // 向左移动
                    if (j > 1) {
                        long long new_mora = dp[i][j][dir] + a[i][j - 1];
                        if (new_mora < 0) continue;
                        new_mora = min(new_mora, k);
                        if (new_mora > dp[i][j - 1][0]) {
                            dp[i][j - 1][0] = new_mora;
                        }
                    }
                    
                    // 向右移动
                    if (j < m) {
                        long long new_mora = dp[i][j][dir] + a[i][j + 1];
                        if (new_mora < 0) continue;
                        new_mora = min(new_mora, k);
                        if (new_mora > dp[i][j + 1][1]) {
                            dp[i][j + 1][1] = new_mora;
                        }
                    }
                    
                    // 向下移动
                    long long new_mora = dp[i][j][dir] + a[i + 1][j];
                    if (new_mora < 0) continue;
                    new_mora = min(new_mora, k);
                    if (new_mora > dp[i + 1][j][0]) {
                        dp[i + 1][j][0] = new_mora;
                    }
                    if (new_mora > dp[i + 1][j][1]) {
                        dp[i + 1][j][1] = new_mora;
                    }
                }
            }
        }
        
        // 寻找最后一行的最大值
        long long max_mora = -1;
        for (int j = 1; j <= m; ++j) {
            max_mora = max(max_mora, max(dp[n][j][0], dp[n][j][1]));
        }
        
        cout << (max_mora >= 0 ? max_mora : -1) << endl;
    }
    
    return 0;
}