Maximum Sum Sub-grid

Given a two-dimensional grid of integers with ( N ) rows and ( M ) columns, your task is to compute the maximum sum over all possible contiguous sub-grids. A sub-grid is defined by selecting a submatrix of the grid. Formally, if we denote ( grid[i][j] ) as the element in the ( i )th row and ( j )th column (with 1-based indexing), then a sub-grid defined by its top-left corner ( (i_1, j_1) ) and bottom-right corner ( (i_2, j_2) ) (where ( 1 \le i_1 \le i_2 \le N ) and ( 1 \le j_1 \le j_2 \le M )) has a sum given by: [ S = \sum_{i=i_1}^{i_2} \sum_{j=j_1}^{j_2} grid[i][j] ] Your goal is to find the maximum value of ( S ) among all possible sub-grids.

We recommend using a prefix sum technique to efficiently compute sub-grid sums.

inputFormat

The first line contains two integers ( N ) and ( M ) separated by a space, representing the number of rows and columns of the grid respectively. Each of the next ( N ) lines contains ( M ) space-separated integers representing the grid's rows.

outputFormat

Output a single integer which is the maximum sum of any sub-grid in the given grid.## sample

3 3
1 2 3
4 5 6
7 8 9

45