Maximum Sum Rectangle

Given a two-dimensional grid of integers, your task is to find the maximum sum over all possible rectangles (i.e., submatrices) within the grid. A rectangle is defined by selecting a contiguous set of rows and a contiguous set of columns. The grid is guaranteed to have at least one cell, and note that the maximum sum may be negative if all numbers are negative.

An effective approach is to fix the left and right boundaries of the rectangle and then compute the cumulative sum for each row within these boundaries. By applying Kadane's algorithm on these cumulative row sums, you can determine the maximum subarray sum which corresponds to the maximum sum rectangle for that particular segment. Iterating over all possible pairs of column boundaries will yield the solution.

The input size constraints are moderate, so an algorithm with a time complexity of O(M²·N) is acceptable.

inputFormat

The first line of input contains two space-separated integers N and M (1 ≤ N, M ≤ 1000), representing the number of rows and columns respectively. This is followed by N lines, each containing M space-separated integers describing the grid.

outputFormat

Output a single integer representing the maximum sum of a rectangle (submatrix) in the given grid.## sample

3 3
-1 -2 -3
-4 5 -6
-7 -8 9

9