题目背景

赛时提醒：格子可以重复经过，但分数只算一次。

题目描述

小 A 有一个 $n\times m$ 的网格，每个格子上都写着一个数字。为方便描述，令左上角的网格为 $(1,1)$，右下角的网格为 $(n,m)$。

小 A 可以进入最下方第 $n$ 行的任意一个网格，并按照以下规则进行游戏：

• 设小 A 第一次进入第 $i$ 行的位置为 $(i,r_i)$：
  如果小 A 在 $(i,r_i)$，则他只能向左或向上跳。否则他可以向左，向右或向上跳。
• 小 A 不能跳出网格，除非他在第 $1$ 行，这代表结束整场游戏。

定义一局游戏的得分为所有小 A 经过的格子上的数字之和。小 A 想请你帮他求出得分的最小值。

输入格式

第一行两个整数 $n,m$，分别表示网格的行数和列数。

第二至 $n+1$ 行每行 $m$ 个整数 $a_{i,j}$，表示 $(i,j)$ 上的数。

输出格式

一行一个整数，表示最小值。

3 3
-1 -3 2
5 -1 -6
-3 7 -6

-17

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

-2

4 4
-1 2 -3 3
-7 -8 -9 -10
-7 20 -3 15
-8 7 0 -1

-32

17 17
536854 594409 871941 -388369 465282 -638502 -121382 -481711 -648747 583148 -407200 -756103 225750 685372 -952316 -115958 688880
-248927 927601 -41187 -729045 -902796 -714842 537911 -972691 646275 -968170 811593 -288461 -492905 954416 455549 839671 927565
317945 317920 -182592 -477 239886 747388 -323625 132984 -147642 637483 948110 750134 450272 -689049 862925 -327794 5865
196810 600825 -547716 873435 -389664 882011 -708186 504812 955352 -657431 -963785 -899423 671938 -770932 -428505 204660 -235382
592361 -686010 805643 -168792 871936 -334335 402655 783215 -315411 480760 371553 -87790 -111152 142452 918172 968088 364749
200836 914812 962142 -276470 757612 -369974 955746 -740349 -218873 976129 94337 -853562 69100 -479860 865764 -865684 -782689
-977548 -226536 197351 516125 137800 -391378 -392070 -954935 -399763 284345 -752733 195962 268045 800832 916405 578799 782717
-111876 -384522 785558 -663839 -346670 317823 -902413 -138975 794147 -377010 -370134 925156 333264 -827840 859848 773995 -335011
495949 -158831 446359 962836 -861756 936842 533809 -58318 -462176 561405 -127056 -497496 -636673 -312588 -354065 -489258 926614
603167 -154853 601062 951736 758952 -290610 838384 -455373 -823858 293098 782955 -711867 739231 -835281 -940599 938774 389756
-762794 -788479 -122327 -608246 998569 -70814 -198006 -361373 658973 -811815 -26348 240052 251877 -660298 -390790 558411 -90995
213545 492431 847902 -681087 -721770 -482897 -577178 -400679 712628 -943805 -613025 927604 867612 -753902 -235086 -60571 445511
901422 -769346 -655924 638444 188703 964292 865767 -298677 -245870 643123 -87216 -18374 -115040 -954311 -220506 919822 -183816
-576494 -481376 139875 360147 411997 437956 755645 874372 130352 -770235 -708813 850918 -835413 -426540 62763 722776 767682
-237305 -121638 -273740 518922 -423961 690214 -253799 571892 915095 586784 670083 -764317 14014 -103481 -750401 325979 70672
323842 988625 859616 920791 -749116 -660548 302396 408853 -944605 732263 -38368 223609 -484449 712951 831842 -200066 -965163
-659884 172567 -482821 -666287 42438 -113937 -539200 -57775 -558423 116068 532754 -440321 456398 -216316 293270 771477 583186

-28761600

提示

「样例说明」

样例 $1$ 的解释如图所示：

「数据范围与约定」

本题采用捆绑测试。

• Subtask 1（3 points）：$a_{i,j}\leq 0$。
• Subtask 2（12 points）：$n,m\leq 5$。
• Subtask 3（15 points）：$n=2$。
• Subtask 4（18 points）：$n,m\leq 90$。
• Subtask 5（22 points）：$n,m\leq 400$。
• Subtask 6（30 points）：无特殊限制。

对于 $100\%$ 的数据：$1\leq n,m\leq 10^3$，$-10^6 \leq a_{i,j}\leq 10^6$。

---

「题目来源」

Sweet Round 05 A。
idea & solution：Alex_Wei。