544. Max Sum of Rectangle No Larger Than K

Given a matrix and an integer k, return the maximum sum of any rectangle (a contiguous sub-matrix) whose sum is no larger than k. It is guaranteed at least one such rectangle exists. The input is JSON {matrix, k}.

Input: JSON {matrix, k}.

Output: Integer — the maximum rectangle sum <= k.

Examples

Input: {"matrix":[[1,0,1],[0,-2,3]],"k":2}
Output: 2
Explanation: A rectangle sums to exactly 2.

Input: {"matrix":[[2,2,-1]],"k":3}
Output: 3
Explanation: Best sum not exceeding 3.

Constraints

• 1<=rows,cols<=100
• -10^5<=value<=10^5

Asked by