國際刷牙奧林匹亞（International Olympiad in tooth brushIng，簡稱 IOI），是一年一度舉辦的國際競賽，目的是在考驗選手的刷牙能力，臺灣國際刷牙奧林匹亞（Taiwan Olympiad in tooth brushIng，簡稱 TOI），每年會選出一位刷牙很強的國手代表臺灣參賽。
這裡是 TOI，由於我們 IOI 2024 的刷牙選手 ＳＪＹ 攜帶電動牙刷進入考場而被取消資格，已緊急從建中徵招職業刷牙選手 SJY (Shih GPow)，沖擊 IOI 2025 滿分金。
IOI 2025 Day 1 Problem 1 如下：有 $n$ 排牙齒，每排牙齒有 $m$ 顆，第 $i$ 排的第 $j$ 顆牙齒有一個整數的爽度 $a_{i,j}$，$a_{i,j}$ 可能有正有負，$a_{i,j}\ge 0$ 代表刷了牙齒變乾淨會很開心，$a_{i,j}<0$ 代表刷了會牙齒痛。
SJY 要在第 $i$ 排的牙齒選一個區間 $[l_i,r_i]$（$1\le l_i\le r_i\le m$） 刷牙，他的爽適度 $S$ 會是每排牙齒選的區間的爽度總和，也就是 $S=\sum\limits_{i=1}^ n\sum\limits_{j=l_i}^ {r_i}a_{i,j}$，並且 SJY 第 $i$（$1\le i<n$） 排牙齒選的區間要滿足一個條件：$[l_i,r_i]$ 包含 $[l_{i+1},r_{i+1}]$ 或是$[l_{i+1},r_{i+1}]$ 包含 $[l_i,r_i]$（如果刷牙區間沒有包含關係會導致牙齦流血），也就是對於所有 $1\le i<n$，要滿足 $1\le l_i\le l_{i+1}\le r_{i+1}\le r_i\le m$ 或是 $1\le l_{i+1}\le l_i\le r_i\le r_{i+1}\le m$。
題目要求 SJY 每排選的刷牙區間在滿足條件下，爽適度 $S$ 最大，請你幫幫他！
第一行有兩個正整數 $n,m$，代表有幾排牙齒和每排牙齒有幾顆。
接下來 $n$ 行，第 $i$ 行有 $m$ 個整數 $a_{i,1}\sim a_{i,m}$，代表第 $i$ 排牙齒的爽度。
對於所有測試資料：
輸出一個整數 $S$，代表 SJY 每排選的刷牙區間在滿足條件下，爽適度的最大值。
在範例測資一中，第 $1$ 排牙齒選的刷牙區間 $[l_1,r_1]=[2,4]$ 可以得到最大的 $S=4+(-1)+2=5$。
在範例測資二中，$3$ 排牙齒選的刷牙區間分別為 $[1,3],[1,1],[1,3]$ 可以得到最大的 $S=56$。
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 範例測資 | 0 |
| 2 | 0, 3~18 | $n=1$ | 12 |
| 3 | 1, 5, 13~40 | 恰好存在一個 $a_{i,j}<0$，其餘都 $\ge 0$ | 16 |
| 4 | 0~5, 41~50 | $n,m\le 70$ | 27 |
| 5 | 0~60 | 無其他限制 | 45 |