QaQ

#include <bits/stdc++.h>
using namespace std;
long long a[1005][1005];
long long dp[1005][1005];
int 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];
		}
		for (int i = 2; i <= n + 2; i++) {
			for (int j = 2; j <= m + 2; j++) dp[i][j] = -LLONG_MAX;
		}
		for (int i = 1; i <= m; i++) {
			dp[1][i] = a[1][i];
		}
		for (int i = 1; i < n; i++) {
			bool f = 1;
			while (f) {
				f = 0;
				for (int j = 1; j <= m; j++) {
					long long maxn = dp[i][j];
					if (j != 1 and dp[i][j - 1] != -LLONG_MAX) maxn = max(maxn, dp[i][j - 1] + a[i][j]);
					if (j != m and dp[i][j + 1] != -LLONG_MAX) maxn = max(maxn, dp[i][j + 1] + a[i][j]);
					maxn = max(maxn, dp[i - 1][j] + a[i][j]);
					if (maxn > k) maxn = k;
					if (maxn != dp[i][j]) {
						dp[i][j] = maxn;
						f = 1;
					}
				}
			}
		}
		long long ans = LLONG_MIN;
		for (int i = 1; i <= m; i++) {
			dp[n][i] = dp[n - 1][i] + a[n][i];
			ans = max(ans, dp[n][i]);
		}
		if (ans < 0) ans = -1;
		cout << ans << "\n";
	}
	return 0;
}