#include<bits/stdc++.h>
using namespace std;
struct node {
    int x, y; int mora;
    node(int x, int y, int mora) :x(x), y(y), mora(mora) {};
};
int bfs(vector<vector<int>>& map, int startx, int starty, int initial_mora, int k) {
    queue<node>q;
    int n = map.size(); int m = map[0].size();
    vector<vector<vector<bool>>>visited(n, vector<vector<bool>>(m, vector<bool>(k + 1, false)));
    vector<tuple<int, int>>move = { {0,-1},{0,1},{1,0} };
    initial_mora = min(initial_mora, k);
    node a = node(startx, starty, initial_mora);
    q.push(a); visited[startx][starty][initial_mora] = true;
    int ans = -1;
    while (!q.empty()) {
        int x = q.front().x; int y = q.front().y;
        int mora = q.front().mora; q.pop();
        if (x == n - 1) {
            ans = max(ans, mora);
            continue;
        }
        for (int i = 0; i < 3; i++) {
            int dx = get<0>(move[i]); int dy = get<1>(move[i]);
            int nx = x + dx; int ny = y + dy;
            //越界处理
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
                continue;
            }
            //mora小于0处理
            if (mora + map[nx][ny] < 0) {
                continue;
            }
            int new_mora = min(mora + map[nx][ny], k);
            if (!visited[nx][ny][new_mora]) {
                visited[nx][ny][new_mora] = true;
                q.push({ nx,ny,new_mora });
            }
        }
    }
    return ans;
}
int main() {
    int c, t; scanf("%d%d",&c,&t);
    for (int i = 0; i < t; i++) {
        int n, m, s, k; scanf("%d%d%d%d",&n,&m,&s,&k);
        vector<vector<int>>map(n, vector<int>(m, 0));
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < m; k++) {
                int a; scanf("%d",&a); map[j][k] = a;
            }
        }
        int best = -1;
        for (int i = 0; i < m; i++) {
            int startx = 0; int starty = i;
            if (s + map[0][i] < 0) {
                continue;
            }
            int ans = bfs(map, startx, starty, s + map[0][i], k);
            if (ans != -1) {
                best = max(best, ans);
            }
        }
        printf("%d\n",best);
    }
    return 0;
}