漫遊曼哈頓 (APCS 2026-11 高級)

紐約市的曼哈頓區有工整的棋盤式道路，東西向和南北向的道路交錯出 \(m \times n\) 個路口。由北往南第 \(i\) 列、由西往東第 \(j\) 欄的路口記為 \((i, j)\)，其中 \(1 \le i \le m\)、\(1 \le j \le n\)。

每兩個相鄰的路口之間都有一段道路，每段道路都有一個好玩度（可能是負的）：

• 東西向的道路連接 \((i, j)\) 與 \((i, j+1)\)，往東、往西都可以走。
• 南北向的道路連接 \((i, j)\) 與 \((i+1, j)\)，只能由北往南走，也就是只能從 \((i, j)\) 走到 \((i+1, j)\)。

有兩個人相約到曼哈頓區玩。他們可以任選一個路口出發，沿著道路走，最後在任選的一個路口結束；同一段道路最多只能經過一次。起點和終點可以是同一個路口，這時他們一段路都沒走，好玩度總和是 \(0\)。

請算出他們經過的道路，好玩度總和最大可以是多少。

下圖是範例 2 的棋盤：道路上的數字是那段道路的好玩度，粗線是好玩度總和最大的走法（實心圓點是起點、空心圓圈是終點，箭頭是行進方向）。

輸入格式

第一行有兩個正整數 \(m\) 和 \(n\)，代表路口共有 \(m\) 列、\(n\) 欄。

接下來的 \(m\) 行是東西向道路的好玩度。這 \(m\) 行中的第 \(i\) 行有 \(n-1\) 個整數，其中第 \(j\) 個整數是連接 \((i, j)\) 與 \((i, j+1)\) 的道路的好玩度。

再接下來的 \(m-1\) 行是南北向道路的好玩度。這 \(m-1\) 行中的第 \(i\) 行有 \(n\) 個整數，其中第 \(j\) 個整數是連接 \((i, j)\) 與 \((i+1, j)\) 的道路的好玩度。

同一行的整數之間以一個空白隔開。

限制

• \(2 \le m \le 1000\)
• \(2 \le n \le 1000\)
• 每段道路的好玩度都是 \(-100\) 到 \(100\) 之間（含）的整數

輸出格式

輸出一個整數，代表經過的道路好玩度總和的最大值。因為可以一段路都不走，答案一定大於或等於 \(0\)。

評分說明

每一筆測試資料的執行時間限制均為 \(2\) 秒，依正確通過的測試資料筆數給分。

範例輸入 1

2 5
7 2 -8 4
6 2 -1 2
5 4 -1 -5 -6

範例輸出 1

23

範例解釋 1

從 \((1, 3)\) 出發，先往西走到 \((1, 1)\)，經過的兩段道路好玩度是 \(2\)、\(7\)；再往南走到 \((2, 1)\)，好玩度是 \(5\)；最後往東走到 \((2, 5)\)，經過的四段道路好玩度是 \(6\)、\(2\)、\(-1\)、\(2\)。好玩度總和是 \(23\)，這是最大值：

範例輸入 2

5 5
-1 -1 -1 -1
3 1 4 1
-1 -1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1
-2 -2 -2 -2 -2
-2 -2 -2 -2 -2
-2 12 9 1 7
-2 -2 6 -2 -2

範例輸出 2

23

範例解釋 2

就是上圖的粗線：從 \((2, 5)\) 出發，往西走到 \((2, 1)\)（\(1 + 4 + 1 + 3 = 9\)），往南走到 \((3, 1)\)（\(-2\)），往東走到 \((3, 2)\)（\(-1\)），往南走到 \((4, 2)\)（\(12\)），往東走到 \((4, 3)\)（\(-1\)），再往南走到 \((5, 3)\)（\(6\)）。好玩度總和是 \(23\)，這是最大值：

題目來源

APCS 2026 年 11 月高級實作題第 2 題。

官方未公布題本，題敘依考生考後回憶整理，細節可能與正式試題有出入。