Maximum Submatrix Sum

Given an \(N \times M\) matrix of integers, your task is to determine the maximum sum of any submatrix within it. A submatrix is defined by selecting four indices \(i_1, j_1, i_2, j_2\) such that \(1 \leq i_1 \leq i_2 \leq N\) and \(1 \leq j_1 \leq j_2 \leq M\). The sum of a submatrix is given by:

\(\sum_{i=i_1}^{i_2} \sum_{j=j_1}^{j_2} A_{ij}\)

The submatrix can consist of a single element or cover the entire matrix. Use efficient methods such as applying a 2D version of Kadane's algorithm to solve this problem.

inputFormat

The first line contains two integers (N) and (M) — the number of rows and columns in the matrix. Each of the following (N) lines contains (M) space-separated integers representing the matrix.

outputFormat

Output a single integer representing the maximum sum of any submatrix within the given matrix.## sample

4 5
1 2 -1 -4 -20
-8 -3 4 2 1
3 8 10 1 3
-4 -1 1 7 -6

29