Largest Sum Submatrix

Given a two-dimensional integer matrix \( A \) with dimensions \( M \times N \), your task is to find the contiguous submatrix (a rectangular block of cells) whose elements have the maximum possible sum. A submatrix is defined by two pairs of indices \( (i_1, j_1) \) and \( (i_2, j_2) \) such that the submatrix includes all elements \( A[i][j] \) for \( i_1 \le i \le i_2 \) and \( j_1 \le j \le j_2 \). The sum of a submatrix is given by:

[ S = \sum_{i=i_1}^{i_2} \sum_{j=j_1}^{j_2} A[i][j] ]

Your goal is to compute the maximum such sum over all possible submatrices.

Note: The matrix can contain both positive and negative integers.

inputFormat

The first line of input contains two integers, M and N, representing the number of rows and columns in the matrix respectively.

Each of the following M lines contains N space-separated integers representing the elements of the matrix.

outputFormat

Output a single integer: the maximum sum of any contiguous submatrix of the given matrix.

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

24