Maximum Sum Subgrid

You are given a 2D grid of size (m \times n) that contains integers (both positive and negative). A subgrid is defined as any contiguous rectangular section of the grid. Your task is to find the maximum sum of a subgrid.

A subgrid defined by the upper left corner ((i, j)) and lower right corner ((p, q)) has a sum given by [ S = \sum_{a=i}^{p} \sum_{b=j}^{q} grid[a][b] ]

For example, for the grid below:

1 2 3
4 5 6
7 8 9

The maximum sum is (45), which corresponds to the entire grid. Solve the problem using efficient techniques (e.g. prefix sums) since a brute force solution might be too slow for larger inputs.

inputFormat

The input is given via standard input. The first line contains two integers (m) and (n) (the number of rows and columns, respectively). The next (m) lines each contain (n) space-separated integers representing the grid.

outputFormat

Output a single integer which is the maximum sum of a subgrid.## sample

3 3
1 2 3
4 5 6
7 8 9

45