class Solution {
private:
    vector<vector<int>> s;

    int get(int x1, int y1, int x2, int y2) {
        return s[x2][y2] + s[x1 - 1][y1 - 1] - s[x2][y1 - 1] - s[x1 - 1][y2];
    }

public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        int m = matrix.size();
        int n = matrix[0].size();
        s = vector<vector<int>>(m+1, vector<int>(n+1));

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + matrix[i][j];
            }
        }

        int res = INT_MIN;
        for (int x1 = 1; x1 <= m; ++x1) {
            for (int x2 = x1; x2 <= m; ++x2) {
                set<int> S;
                S.insert(0);
                for (int y2 = 1; y2 <= n; ++y2) {
                    int s2 = get(x1, 1, x2, y2);
                    auto it = S.lower_bound(s2 - k);
                    if (it != S.end()) {
                        res = max(res, s2 - *it);
                    }
                    S.insert(s2);
                }
            }
        }
        return res;
    }
};