Maximum Crop Yield

You are given a two-dimensional field represented as an \(N \times M\) matrix, where each element represents the crop yield of that cell (note that yields can be negative, indicating losses). Your task is to find the rectangular subfield (i.e. submatrix) that gives the maximum possible sum of yields.

This can be mathematically formulated as:

\[ max\_yield = \max_{0 \leq i \leq j < M,\; 0 \leq k \leq l < N} \sum_{p=k}^{l} \sum_{q=i}^{j} a_{pq} \]

If the matrix is empty, the answer is defined as 0.

inputFormat

The first line contains two integers (N) and (M), the number of rows and columns of the field respectively. Each of the next (N) lines contains (M) space-separated integers representing the crop yields in that row.

outputFormat

Output a single integer representing the maximum sum of crop yields in any rectangular subfield.## sample

4 5
1 2 -1 -4 -20
-8 -3 4 2 1
3 8 10 1 3
-4 -1 1 7 -6

29