#include <bits/stdc++.h>
using namespace std;
long long c, t;
long long a[1010][1010];
long long f[1010][1010];
inline bool calc (long long x, long long y, long long n, long long m) {
	if (x >= 1 && x <= n && y >= 1 && y <= m)
		return true;
	else
		return false;
}
inline void bfs (long long start, long long n, long long m, long long s, long long k) {
	queue <pair <long long, long long>> p;
	memset (f, 0, sizeof (f));
	f[1][start] = s + a[1][start];
	if (f[1][start] < 0)
		return;
	p.push ({1, start});
	while (!p.empty()) {
		pair <long long, long long> x = p.front();
		p.pop();
		long long xx = x.first;
		long long yy = x.second;
		if (calc (xx + 1, yy, n , m) && f[xx][yy] + a[xx + 1][yy] >= 0 && f[xx][yy] + a[xx + 1][yy] > f[xx + 1][yy]) {
			p.push ({xx + 1, yy});
			f[xx + 1][yy] = f[xx][yy] + a[xx + 1][yy];
			if (f[xx + 1][yy] > k)
				f[xx + 1][yy] = k;
		}
		if (calc (xx, yy + 1, n , m) && f[xx][yy] + a[xx][yy + 1] >= 0 && f[xx][yy] + a[xx][yy + 1] > f[xx][yy + 1]) {
			p.push ({xx, yy + 1});
			f[xx][yy + 1] = f[xx][yy] + a[xx][yy + 1];
			if (f[xx][yy + 1] > k)
				f[xx][yy + 1] = k;
		}
		if (calc (xx, yy - 1, n , m) && f[xx][yy] + a[xx][yy - 1] >= 0 && f[xx][yy] + a[xx][yy - 1] > f[xx][yy - 1]) {
			p.push ({xx, yy - 1});
			f[xx][yy - 1] = f[xx][yy] + a[xx][yy - 1];
			if (f[xx][yy - 1] > k)
				f[xx][yy - 1] = k;
		}
	}
}
int main() {
	freopen("journey2.in", "r", stdin);
	scanf ("%lld%lld", &c, &t);
	while (t--) {
		long long n, m, s, k;
		scanf ("%lld%lld%lld%lld", &n, &m, &s, &k);
		for (long long i = 1; i <= n; i++)
			for (long long j = 1; j <= m; j++)
				scanf ("%lld", &a[i][j]);
		long long mi = 0;
		for (long long start = 1; start <= m; start++) {
			bfs (start, n, m, s, k);
			long long ma = 0;
			for (long long i = 1; i <= m; i++)
				ma = max (f[n][i], ma);
			mi = max (ma, mi);
		}
		if (mi == 0)
			printf ("-1\n");
		else 
			printf("%lld\n", mi);
	}
	return 0;
}

样例过了