You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

逛菜园

题目描述

WFYZ有一个 $H\times W$ 个格子构成的菜园，处理每个格子的蔬菜都有一个劳累值。其中左上角的格子编号 $(1,1)$，右下角的格子编号为 $(H,W)$。你在菜园里劳动，希望可以获得最小劳累值。

你可以进入最下方第 $H$ 行的任意一个格子，并按照以下规则进行移动：

• 设你第一次进入第 $i$ 行的位置为 $(i,y_i)$： 如果你在一行首次进入的位置 $(i,y_i)$，只能向左或向上移动。否则可你以向左，向右或向上移动。你每到一个格子，都需要干完这个格子的农活，并积累相应的劳累值，才可以离开。格子可以重复经过，但劳累值分数只算一次；劳累值可能为负数，其实就是累并快乐着。 -你只能从第 $1$ 行离开菜园，这代表劳动结束。

你在菜园劳动的最小劳累值是多少。

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

4 3
-2 -3 1
4 -2 -1
3 2 -3
-1 2 3

样例输出 #1

-8

样例 #2

样例输入 #2

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

样例输出 #2

-26

提示

「样例说明」

样例 $2$ 的解释： 从$(4,4)->(4,3)->(3,3)->(2,3)->(2,2)->(2,1)->(2,2)->(2,3)->(1,3)->(1,2)->(1,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$。