Problem Description

Contest Reminder: Cells can be revisited, but scores are only counted once.

Problem Description

Little A has an \( n \times m \) grid, where each cell contains a number. For convenience, the top-left cell is denoted as \( (1,1) \) and the bottom-right cell as \( (n,m) \).

Little A can start from any cell in the bottom row \( n \) and play the game according to the following rules:

• Let \( (i, r_i) \) be the position where Little A first enters row \( i \):
  If Little A is at \( (i, r_i) \), he can only jump left or up. Otherwise, he can jump left, right, or up.
• Little A cannot jump out of the grid unless he is in row 1, which signifies the end of the game.

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

Input Format

The first line contains two integers \( n \) and \( m \), representing the number of rows and columns of the grid, respectively.

The next \( n \) lines each contain \( m \) integers \( a_{i,j} \), representing the number in cell \( (i,j) \).

Output Format

A single integer representing the minimum score.

Sample Input and Output

Input Sample #1

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

Output Sample #1

-17

Input Sample #2

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

Output Sample #2

-2

Input Sample #3

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

Output Sample #3

-32

Input Sample #4

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

Output Sample #4

-28761600

Notes

Sample Explanation

The explanation for Sample 1 is illustrated in the following image:

Data Range and Constraints

This problem uses batched testing.

• 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 restrictions.

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

Problem Source

Sweet Round 05 A.
Idea & Solution: Alex_Wei.

见题面 Input 部分

见题面 Output 部分