Maximum Subgrid Sum

You are given a 2D grid of non-negative integers. Your task is to find the maximum sum of any rectangular subgrid (i.e. a contiguous submatrix) in the given grid.

Let \(grid\) be a matrix of size \(N \times M\), and a subgrid is defined by two pairs of coordinates \((r_1, c_1)\) and \((r_2, c_2)\) with \(1 \leq r_1 \leq r_2 \leq N\) and \(1 \leq c_1 \leq c_2 \leq M\). The sum of such a subgrid is given by:

\(S = \sum_{i=r_1}^{r_2} \sum_{j=c_1}^{c_2} grid[i][j]\)

Your goal is to compute the maximum \(S\) over all possible subgrids.

Note: The input grid will always have at least one element.

inputFormat

The input is read from stdin and consists of:

• The first line contains two integers \(N\) and \(M\), representing the number of rows and columns of the grid.
• The next \(N\) lines each contain \(M\) space-separated integers representing the grid elements.

All numbers are non-negative integers.

outputFormat

Output a single integer to stdout representing the maximum sum of any subgrid in the grid.

## sample

3 3
1 2 3
4 5 6
7 8 9

45