669. Max Sum of Rectangle No Larger Than K

Given a matrix and an integer k, return the maximum sum of any rectangular submatrix such that the sum is no larger than k. The input is JSON {matrix, k}.

Input: JSON {matrix, k}.

Output: Integer — the maximum submatrix sum not exceeding k.

Examples

Input: {"matrix":[[1,0,1],[0,-2,3]],"k":2}
Output: 2
Explanation: The rectangle summing to 2 is the largest not exceeding k.

Input: {"matrix":[[2,2,-1]],"k":3}
Output: 3
Explanation: 2 + 2 - 1 = 3.

Input: {"matrix":[[5]],"k":5}
Output: 5
Explanation: Single cell.

Constraints

• 1<=rows,cols<=100

Asked by