Maximum Submatrix Sum

You are given a matrix with ( n ) rows and ( m ) columns, where each element is an integer (which can be negative or positive). Your task is to find the maximum possible sum of all elements in any submatrix of the given matrix. A submatrix is defined by choosing two rows and two columns such that all elements between these bounds are included. Formally, if we denote the matrix as ( A ) with ( 0 \leq i < n ) and ( 0 \leq j < m ), a submatrix from row ( i_1 ) to ( i_2 ) and column ( j_1 ) to ( j_2 ) has a sum given by: [ S = \sum_{i=i_1}^{i_2} \sum_{j=j_1}^{j_2} A_{ij} ] Your goal is to determine the maximum ( S ) among all possible submatrices. Note that the matrix might be empty (i.e. when ( n=0 ) or ( m=0 )), for which the answer is defined to be 0.

inputFormat

The input is read from standard input (stdin). The first line contains two integers ( n ) and ( m ) (with ( 0 \leq n, m \leq 1000 )). If either ( n ) or ( m ) is 0, it indicates an empty matrix. Otherwise, the next ( n ) lines each contain ( m ) space-separated integers representing the matrix entries.

outputFormat

Output a single integer to standard output (stdout) which represents the maximum submatrix sum calculated from the given matrix.## sample

3 3
1 2 3
4 5 6
7 8 9

45