Maximum Sum Submatrix

Given an n x m matrix of integers, your task is to find the maximum sum of any submatrix. A submatrix is defined as any contiguous block of rows and columns in the matrix.

The sum of a submatrix from row i₁ to i₂ and column j₁ to j₂ is given by:

$$ S = \sum_{i=i_1}^{i_2} \sum_{j=j_1}^{j_2} A_{ij} $$

You are required to compute the maximum such sum over all possible submatrices.

inputFormat

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

The next n lines each contain m integers, representing the elements of the matrix.

outputFormat

Output a single integer, which is the maximum sum of any submatrix in the given matrix.

3 3
1 2 3
4 5 6
7 8 9

45