#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1010;
const long long INF = 1e18;
long long g[N][N], f[N][N];
long long n, m, s, k;

int main()
{
    int c, t;
    scanf("%d%d", &c, &t);
    while (t--)
    {
        for (int i = 0; i <= n + 1; i++)
        {
            for (int j = 0; j <= m + 1; j++)
                f[i][j] = -INF;
        }
        scanf("%lld%lld%lld%lld", &n, &m, &s, &k);
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                scanf("%lld", &g[i][j]);
                if (i == n) continue;
                if (j > 1 && g[i][j - 1] + g[i][j] > 0)
                {
                    if (g[i][j - 1] >= 0) g[i][j - 1] = k;
                    if (g[i][j] >= 0) g[i][j] = k;
                }
            }
        }
        for (int j = 1; j <= m; j++)
            f[1][j] = min(k, g[1][j] + s);
        for (int i = 1; i <= n - 1; i++)
        {
            for (int j = 1; j <= m; j++)
            {
            	if (f[i - 1][j] < 0) continue;
                long long temp = min(k, f[i - 1][j] + g[i][j]);
                f[i][j] = max(f[i][j], temp);
            }
            for (int j = 1; j <= m; j++)
            {
                long long temp = min(k, f[i][j - 1] + g[i][j]);
                f[i][j] = max(f[i][j], temp);
            }
            for (int j = m; j >= 1; j--)
            {
                long long temp = min(k, f[i][j + 1] + g[i][j]);
                f[i][j] = max(f[i][j], temp);
            }
            for (int j = 1; j <= m; j++)
            {
                long long temp = min(k, f[i][j - 1] + g[i][j]);
                f[i][j] = max(f[i][j], temp);
            }
            for (int j = m; j >= 1; j--)
            {
                long long temp = min(k, f[i][j + 1] + g[i][j]);
                f[i][j] = max(f[i][j], temp);
            }
        }
        for (int j = 1; j <= m; j++)
        {
        	if (f[n - 1][j] < 0) continue;
            long long temp = min(k, f[n - 1][j] + g[n][j]);
            f[n][j] = max(f[n][j], temp);
        }
        long long ans = -1;
        for (int j = 1; j <= m; j++)
            ans = max(ans, f[n][j]);
        printf("%lld\n", ans);
    }
    return 0;
}