Maximum Sum Rectangle with Condition

Given a two-dimensional integer matrix matrix and an integer k, return the largest sum of a rectangle ≤ k.

Constraints

• n, m ≤ 100 where n and m are the number of rows and columns in matrix.

https://binarysearch.com/problems/Maximum-Sum-Rectangle-with-Condition

Examples

Example 1

Input

• matrix =

[[ 2,-2],
 [ 3, 2]]

• k = 6

Output

• answer = 5

Explanation

We can take the rectangle [2, 3] to get sum of 5.

Solution