Some CS 314 students have asked you for help on a problem from their first homework assignment. You didn't get all of the details about the problem bounds, so you've set some limits that seem reasonable to you. Can you help them solve the problem?
You are given a rectangular $$$N \times M$$$ grid $$$g$$$ of integers, and the homework problem asks you to compute the maximum possible sum of entries in a contiguous rectangular sub-grid of the given grid. (A $$$0 \times 0$$$ sub-grid is a valid sub-grid and its entries sum to $$$0$$$. The entire grid $$$g$$$ also counts as a sub-grid of itself.)
In other words, compute $$$$$$\max_{0 \leq l \leq r \leq M \\ 0 \leq t \leq b \leq N} \sum_{i=l}^{r-1} \sum_{j=t}^{b-1} g_{ji}$$$$$$ where $$$g_{ji}$$$ is the grid entry in row $$$j$$$, column $$$i$$$.
The first line of input contains two space-separated integers $$$N$$$ and $$$M$$$ $$$(1 \leq N, M \leq 500)$$$, the number of rows and columns in the grid $$$g$$$, respectively.
The next $$$N$$$ lines each contain $$$M$$$ space-separated integers each and describe the entries of $$$g$$$. All entries are in the range $$$[-10^6, 10^6]$$$.
Print a single integer: the sum of the entries in the contiguous sub-grid of $$$g$$$ that maximizes this sum.
4 47 -3 4 2-1 8 -5 63 0 -9 10-4 5 1 -8
22
2 3-3 -1 -4-1 -5 -9
0
4 5-108793 -29395 -608138 -722622 407621702232 -619216 391815 -778753 568439426028 69966 885259 624653 -531945887849 -702803 -494114 655225 155269
2352063
In the first sample, the sub-grid using rows $$$1$$$ through $$$3$$$ and columns $$$1$$$ through $$$4$$$ has sum $$$22$$$, which is maximum.
In the second sample, every entry is negative, so the valid empty sub-grid has the maximum sum, $$$0$$$.
In the third sample, the sub-grid using rows $$$3$$$ and $$$4$$$ and columns $$$1$$$ through $$$4$$$ has the maximum sum, $$$2352063$$$.
