787 . 倉鼠
TopCoder
Description
小晴養了一隻倉鼠，為了讓倉鼠學習，小晴設計了一個 $N \times M$ 的表格，每個格子上都有堅果，並且每個堅果都有不同的好吃度。小晴希望倉鼠從表格最左上角的格子開始走到最右下角的格子，但是途中只能夠往下或往右走，路途中遇到的堅果都必須吃掉，而小晴希望倉鼠在看完地圖後能夠找到一條路徑讓吃到的堅果好吃度總和最大。但倉鼠只是一隻倉鼠，牠根本什麼都不會，請你各位幫幫這隻可憐的倉鼠吧！
Input Format
輸入第一行有兩個正整數 $N, M (1 \leq N, M \leq 10^ 5, 1 \leq N \times M \leq 10^ 5)$，分別代表表格的長度與寬度。
接下來的 $N$ 行，每一行都有 $M$ 個數字 $a_{ij} (1 \leq a_{ij} \leq 10^ 9)$，代表該格子堅果的好吃度。
Output Format
請輸出一個整數代表倉鼠可以吃到的最大好吃度總和。
Sample Input 1
2 2
1 5
2 1
1 5
2 1
Sample Output 1
7
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 0~10 | 無額外限制 | 100 |