P6649 “SWTR-5” Grid

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

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.

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 one integer in one line, representing the minimum value.

“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](https://www.luogu.com.cn/contest/28195) A. idea & solution: [Alex_Wei](https://www.luogu.com.cn/user/123294). Translated by ChatGPT 5