Maximum Sub-grid Sum

In this problem, you are given a grid (matrix) of integers with ( R ) rows and ( C ) columns. Your task is to find the maximum sum of any contiguous sub-grid (i.e. submatrix). A contiguous sub-grid is defined by a pair of rows and a pair of columns forming a rectangular block in the original grid.

One way to solve this problem is to fix the left and right column boundaries and compress the grid into a one-dimensional array by summing the rows within these boundaries. Then, you can apply Kadane's algorithm to quickly find the maximum contiguous subarray sum for that one-dimensional array. By iterating over all pairs of columns, the maximum sum among all such sub-grids can be found.

The key formula used in Kadane's algorithm is: [ current = \max(x, current + x) \quad \text{and} \quad best = \max(best, current) ] where ( x ) is an element in the array.

inputFormat

The first line of the input contains two integers \( R \) and \( C \), representing the number of rows and columns of the grid, respectively.

The following \( R \) lines each contain \( C \) space-separated integers representing the rows of the grid.

outputFormat

Output a single integer representing the maximum sum obtainable from any contiguous sub-grid of the given grid.

## sample

3 3
1 2 -1
-3 4 2
1 -1 3

9

</p>