Maximum Flower Collection in a Subgrid

You are given a garden represented as a 2D grid with rows and cols where each cell contains an integer which may be positive, negative, or zero. This integer represents the number of flowers in that cell. Your task is to find the maximum number of flowers that can be collected by choosing any rectangular subgrid (contiguous block) from the garden.

Formally, if the garden is represented by a matrix \( A \) of size \( rows \times cols \), you need to find the maximum sum over all submatrices of \( A \). The submatrix is defined by two pairs of indices \( (i_1, j_1) \) and \( (i_2, j_2) \) where \( 0 \leq i_1 \leq i_2 < rows \) and \( 0 \leq j_1 \leq j_2 < cols \), and the sum is computed as:

[ S = \sum_{i=i_1}^{i_2} \sum_{j=j_1}^{j_2} A[i][j] ]

It is guaranteed that the grid has at least one cell.

inputFormat

The first line contains two integers, rows and cols (1 ≤ rows, cols ≤ 1000), representing the number of rows and columns in the garden respectively.

The next rows lines each contain cols spaced integers, where the \( i \)-th line represents the \( i \)-th row of the garden's grid. Each integer represents the number of flowers in that cell.

The input is given via stdin.

outputFormat

Output a single integer: the maximum number of flowers that can be collected from any rectangular subgrid. The output should be printed via stdout.

3 3
1 2 3
4 5 6
7 8 9

45