Background

Reminder during the contest: You may pass through a cell multiple times, but its value is counted only once.

Problem Description

Xiao A has an $n \times m$ grid, and each cell contains a number. For convenience, let the top-left cell be $(1,1)$ and the bottom-right cell be $(n,m)$.

Xiao A may enter any cell in the bottom row $n$, and play the game by the following rules:

• Let the position where Xiao A enters row $i$ for the first time be $(i,r_i)$:
  If Xiao A is at $(i,r_i)$, then he can only jump left or up. Otherwise, he can jump left, right, or up.
• Xiao A cannot jump out of the grid, unless he is in row $1$, which means the whole game ends.

The score of one game is defined as the sum of the numbers on all cells that Xiao A passes through. Xiao A wants you to help him find the minimum possible score.

Input Format

The first line contains two integers $n, m$, representing the number of rows and columns of the grid.

Lines $2$ to $n+1$ each contain $m$ integers $a_{i,j}$, representing the number on $(i,j)$.

Output Format

Output one integer in one line, representing the minimum value.

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

Hint

“Sample Explanation”

The explanation for sample $1$ is shown in the figure:

“Constraints and Notes”

This problem uses bundled tests.

• 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): no special constraints.

For $100\%$ of the testdata: $1\leq n,m\leq 10^3$, $-10^6 \leq a_{i,j}\leq 10^6$.

“Source”

Sweet Round 05 A.
idea & solution: Alex_Wei.

Translated by ChatGPT 5