Maximum Sum Subrectangle

Given a 2D grid of integers, your task is to find the maximum sum of any non-empty subrectangle within the grid. A subrectangle is defined by choosing a contiguous block of rows and columns.

Formally, for a subrectangle that spans rows \(i\) to \(j\) and columns \(k\) to \(l\), its sum is given by \[ S = \sum_{p=i}^{j} \sum_{q=k}^{l} grid[p][q] \] The objective is to maximize \(S\) over all possible subrectangles.

inputFormat

The first line contains two integers \(m\) and \(n\) representing the number of rows and columns in the grid respectively. This is followed by \(m\) lines, each containing \(n\) integers separated by spaces, which represent the grid.

outputFormat

Output a single integer — the maximum sum of any non-empty subrectangle in the grid.

3 4
1 2 -1 4
-5 -2 3 6
2 2 -5 1

12