Maximum Sum Subgrid

Given a 2D grid (matrix) of integers with dimensions \(N \times M\), your task is to find the maximum sum of any contiguous subgrid. A subgrid is defined as any rectangular section of the original grid.

You are required to compute the sum of every possible subgrid and output the maximum sum among them. For example, if the grid is as follows:

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

Then one of the subgrids could be:

4   5
-2  3

The sum of this subgrid is \(4 + 5 - 2 + 3 = 10\), and you are to determine the maximum sum obtainable over all subgrids. Note that the subgrid can be as small as a single element or as large as the entire grid.

Input Constraints:

• \(1 \leq N, M \leq 300\)
• \(|grid[i][j]| \leq 10^4\)

Hint: You might consider using a 2D prefix sum technique together with a variant of Kadane's algorithm to achieve an efficient solution.

inputFormat

The input is given via standard input and is formatted as follows:

1. The first line contains two integers \(N\) and \(M\) representing the number of rows and columns in the grid.
2. The next \(N\) lines each contain \(M\) integers separated by spaces, denoting the grid values.

For example:

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

outputFormat

Output a single integer, which is the maximum sum of any subgrid within the given grid. The output should be printed to standard output.

For the above sample, the output should be:

11

## sample

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

11