P6649 「SWTR-5」Grid

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

小 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)$ 上的数。

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

「样例说明」 样例 $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](https://www.luogu.com.cn/contest/28195) A。 idea & solution：[Alex_Wei](https://www.luogu.com.cn/user/123294)。