Maximum Sum Subrectangle

You are given a grid with \(N\) rows and \(M\) columns, where each cell contains an integer (which can be negative, zero, or positive). Your task is to find the subrectangle (i.e. a contiguous sub-grid) whose sum of elements is maximum.

More formally, let the grid be represented as \(a_{ij}\) for \(1 \leq i \leq N\) and \(1 \leq j \leq M\). You need to find indices \(i_1, j_1, i_2, j_2\) with \(1 \leq i_1 \leq i_2 \leq N\) and \(1 \leq j_1 \leq j_2 \leq M\) such that the sum \[ S = \sum_{i=i_1}^{i_2} \sum_{j=j_1}^{j_2} a_{ij} \] is maximized. Print the maximum sum.

Note: The grid may include negative numbers.

inputFormat

The first line of input contains two integers \(N\) and \(M\) separated by a space.

Then follow \(N\) lines, each containing \(M\) integers separated by spaces, representing the grid.

outputFormat

Output a single integer: the maximum sum obtainable from any subrectangle of the grid.

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

29