class Solution {
public:
    inline int valid (int r , int c,  vector<vector<int>> &grid)
    {
        return r < grid.size() && c < grid[0].size() ? grid[r][c] : 0;
    }
    inline int get_sum (int row1, int col1, int row2, int col2, vector<vector<int>> &grid)
    {
         return valid(row2, col2,grid) - valid(row1 - 1, col2,grid) - valid(row2 , col1 - 1,grid) + valid (row1 -1, col1 -1,grid);
    }



    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {

        vector <int> cur_col;
        vector<vector<int>> grid = matrix;

        int rows = matrix.size();
        int cols = matrix[0].size();

        for (int i = 0 ; i< rows ; i ++ )
            for (int j = 0 ; j < cols ; j ++)
                grid[i][j] += valid (i-1, j,grid) + valid(i,j-1,grid) - valid(i-1,j-1,grid);

        int res = INT_MIN;
        for (int top_left_y = 0 ; top_left_y < rows ; top_left_y++)
        {
            for (int top_left_x  = 0 ; top_left_x < cols; top_left_x++)
        {
            for ( int bottom_right_y = top_left_y ; bottom_right_y < rows ; bottom_right_y++ )
            {
                 for (int bottom_right_x = top_left_x ; bottom_right_x < cols; bottom_right_x++)
                 {

                     int cur_sum = get_sum (top_left_y, top_left_x, bottom_right_y, bottom_right_x,grid);

                     if (cur_sum > k)
                         continue;
                     res = max(res, cur_sum);
                  }
            }
        }

        }


        return res;
    }
};
/*


*/
 int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {

        int rows = matrix.size();
        int cols = matrix[0].size();

        for (int i = 0 ; i< rows ; i ++ )
            for (int j = 1 ; j < cols ; j ++)
                matrix[i][j] += matrix[i][j-1];

        int res = INT_MIN;
        for (int top_left_x  = 0 ; top_left_x < cols; top_left_x++)
            for (int bottom_right_x = top_left_x ; bottom_right_x < cols; bottom_right_x++) {
                vector<int> x(rows);
                for(int r = 0; r < rows; r++) {
                    x[r] = matrix[r][bottom_right_x] - (top_left_x == 0? 0 : matrix[r][top_left_x-1]);
                }
                int cur_sum = 0;
                set<int> prevSums;
                prevSums.insert(0);
                for(int r = 0; r < rows; r++) {
                    cur_sum += x[r];
                    int req = cur_sum - k;
                    auto it = prevSums.lower_bound(req);
                    if(it != prevSums.end()){
                        res = max(res, cur_sum - *it);
                    }
                    prevSums.insert(cur_sum);
                }
        }


        return res;
    }
};
/*


*/