2182 . 幸運表格 (Lucky)
TopCoder
Description
幸運表格是一種古老的遊戲，在 $m \times n$ 的表格中，每一個格子都被預先填入一個整數；接著玩家需要在蒙眼的狀況下選定一個格子做為他的起始位置，之後這位玩家只能在表格中「向右」或者「向下」移動，並且加上所有經過的格子上的整數數值，直到玩家的移動超出這個 $m \times n$ 的表格；此時，玩家所經過的所有數值的總和即為他的「幸運數」。您的任務是，給定一個 $m \times n$ 的表格，找出所有可能的幸運數中的最大值。
例如：在右圖一個 $5 \times 5$ 的表格中，每個格子分別被填入一個整數值接著，玩家從第二列第三欄的格子開始，依序往「下」「下」「右」「下」「下」移動，接著離開這個表格，則他的幸運數即為 $8\ – 6 + 7\ – 3 + 4 = 10$。然而，在這個例子中，若要達到最大可能的幸運數，則玩家需要從第三列的第一欄起始，接著往「右」「下」「右」「右」「下」「下」移動，其所達到的幸運數為 $15$。
Input Format
輸入的第一行有二個以一個空白符號隔開的正整數 $m$ 和 $n$，代表表格的列數和行數。接著 $m$ 行中，每一行有 $n$ 個空白符號隔開的整數，其中第 $i$ 行的第 $j$ 個整數，即代表表格中第 $i$ 列第 $j$ 欄的格子上的數字。每一個格子中的整數，必定大於 $-100$ 且小於 $100$。
Output Format
請根據輸入的資料，輸出該個幸運表格所可能產出的最大幸運數。
Sample Input 1
5 -2
-3 1
Sample Output 1
Sample Input 2
-1 7 -8 10 -5
-4 -9 8 -6 0
5 -2 -6 -6 7
-7 4 7 -3 -3
7 1 -6 4 -9
Sample Output 2
Hints
本題共有四組測試資料，每組可有多筆測試資料：
第一組測試資料 $m = n = 2$，共 15 分。
第二組測試資料 $2 < m = n \leq 5$，共 20 分。
第三組測試資料 $5 < m = n \leq 100$，共 28 分。
第四組測試資料 $5 < m \leq 1000, 5 < n \leq 1000$，共 37 分。
Problem Source
107北市賽
testdata set by Omelet
註： 這裡的測資裡面最小的數字可以到 -1000，因為暫時應該不需要 rejudge 所以在這邊聲明就好。
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~4 | $m = n = 2$ | 15 |
| 2 | 5~19 | $2 < m = n \leq 5$ | 20 |
| 3 | 20~29 | $5 < m = n \leq 100$ | 28 |
| 4 | 20~39 | $5 < m, n \leq 1000$ | 37 |