#include<bits/stdc++.h>
using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

template<typename X, typename Y>
bool chmax(X& a, Y b) { return (a < b) ? a = b, 1 : 0; }
template<typename X, typename Y>
bool chmin(X& a, Y b) { return (a > b) ? a = b, 1 : 0; }

const ll INF = 1e18;
const int N = 1005;

int n, m, k, T, a[N][N];
ll P[N][N];

inline ll get(int i, int j, int x) { return P[i][j] - P[i - x][j] - P[i][j - x] + P[i - x][j - x]; }

bool check(int x) {
    for (int i = x; i <= n; i++)
        for (int j = x; j <= m; j++)
            if (get(i, j, x) <= T)
                return true;
    return false;
}

void solve() {
    cin >> n >> m >> k >> T;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + a[i][j];
        }
    if (k == 1) {
        int low = 1, high = n, ans = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (check(mid)) ans = mid, low = mid + 1;
            else high = mid - 1;
        }
        cout << ans * ans << '\n';
        return;
    }
    int X = min(n, m);
    vector<vector<ll>> top(n + 5, vector<ll>(X + 5, INF)), bottom(n + 5, vector<ll>(X + 5, INF));
    vector<vector<ll>> left(m + 5, vector<ll>(X + 5, INF)), right(m + 5, vector<ll>(X + 5, INF));
    for (int x = 1; x <= X; x++) {
        for (int i = x; i <= n; i++)
            for (int j = x; j <= m; j++) {
                ll S = get(i, j, x);
                if (S > T) continue;
                chmin(top[i][x], S); chmin(bottom[i - x + 1][x], S);
                chmin(left[j][x], S); chmin(right[j - x + 1][x], S);
            }
        for (int i = 1; i <= n; i++) chmin(top[i][x], top[i - 1][x]);
        for (int i = n; i >= 1; i--) chmin(bottom[i][x], bottom[i + 1][x]);
        for (int j = 1; j <= m; j++) chmin(left[j][x], left[j - 1][x]);
        for (int j = m; j >= 1; j--) chmin(right[j][x], right[j + 1][x]);
    }
    int ans = 0;
    for (int i = 1; i < n; i++) {
        int X1 = min(i, X), X2 = min(n - i, X);
        for (int x1 = 1; x1 <= X1; x1++) {
            if (top[i][x1] > T) continue;
            for (int x2 = 1; x2 <= X2; x2++)
                if (top[i][x1] + bottom[i + 1][x2] <= T)
                    ans = max(ans, x1 * x1 + x2 * x2);
        }
    }
    for (int j = 1; j < m; j++) {
        int X1 = min(j, X), X2 = min(m - j, X);
        for (int x1 = 1; x1 <= X1; x1++) {
            if (left[j][x1] > T) continue;
            for (int x2 = 1; x2 <= X2; x2++)
                if (left[j][x1] + right[j + 1][x2] <= T)
                    ans = max(ans, x1 * x1 + x2 * x2);
        }
    }
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    #define TASK "LAND"
    if (fopen(TASK".INP", "r")) {
        freopen(TASK".INP", "r", stdin);
        freopen(TASK".OUT", "w", stdout);
    }

    int tests = 1; // cin >> tests;
    while (tests--) solve();

    return 0;
}