Maximum Sum Submatrix

You are given a two-dimensional grid with m rows and n columns, where each cell contains an integer. Your task is to find the contiguous submatrix (a block of consecutive rows and columns) that has the maximum possible sum, and output that sum.

The solution involves applying an extension of Kadane's algorithm to 2D arrays. If we denote the grid by \(A\), then any submatrix sum is defined as:

\(S = \sum_{i=r_1}^{r_2} \sum_{j=c_1}^{c_2} A[i][j]\)

You are required to read input from standard input (stdin) and write the result to standard output (stdout).

inputFormat

The first line of input contains two integers m and n (1 ≤ m, n ≤ 1000), representing the number of rows and columns of the grid. Each of the following m lines contains n integers separated by spaces, representing the grid values.

outputFormat

Output a single integer which is the maximum sum of any contiguous submatrix in the grid.

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

24