Maximum Submatrix Sum

You are given an $N \times M$ matrix $A$. Find the maximum sum of any subrectangular submatrix of this matrix.

Here, a subrectangular submatrix is defined as a contiguous submatrix formed by selecting any rectangular section of the given matrix $A$, such that the submatrix includes all rows and columns between two specified pairs of indices $(r_1, c_1)$ and $(r_2, c_2)$, where $1 \le r_1 \le r_2 \le N$ and $1 \le c_1 \le c_2 \le M$, plus the case when the submatrix is empty.

The first line of input contains two space-separated integers: $N$ and $M$, denoting the size of the matrix. ($1 \le N \le M \le 100\,000;$ $1 \le NM \le 100\,000$)

The next $N$ lines of input contain $NM$ integers, where each line has $M$ space-separated integers, denoting the value of the matrix. Here, the $j$-th integer of the $i$-th line denotes $A_{ij}$. ($-10\,000 \le A_{ij} \le 10\,000$)

Output the maximum sum of any subrectangular submatrix on a single line.

(For Sogang students:) Note that this problem is an improvised version that matches the format of a problem in a general programming contest. While in the exam, the original scoring was:

• $35$ points for Subtask 1.
• $25$ points for Subtask 2.
• $35$ points for Subtask 3.
• $5$ points for Subtask 4.