Problem 61: Maximum Sum Submatrix No Larger Than K

Problem Statement: Given an m x n matrix and an integer k, find the maximum sum of any non-empty submatrix such that the sum is no larger than k.

Input

The first line contains three integers m, n, and k. Each of the next m lines contains n space-separated integers.

Output

Print the maximum sum of any submatrix with sum <= k.

Examples


Input:
2 3 2
1 0 1
0 -2 3

Output:
2

Solution Explanation

For each pair of rows, collapse the 2D array into a 1D array and then use a balanced BST or prefix sum technique to find the best subarray sum no larger than k.

Solution in C++


#include 
#include 
#include 
#include 
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m, n, k; 
    cin >> m >> n >> k;
    vector> matrix(m, vector(n));
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++)
            cin >> matrix[i][j];
    }
    int ans = -1000000000;
    for(int top = 0; top < m; top++){
        vector dp(n, 0);
        for(int bottom = top; bottom < m; bottom++){
            for(int j = 0; j < n; j++){
                dp[j] += matrix[bottom][j];
            }
            set bst;
            bst.insert(0);
            int curSum = 0;
            for(int val : dp){
                curSum += val;
                auto it = bst.lower_bound(curSum - k);
                if(it != bst.end()){
                    ans = max(ans, curSum - *it);
                }
                bst.insert(curSum);
            }
        }
    }
    cout << ans << "\n";
    return 0;
}