#798. 方格取数

方格取数

题目描述

设有 n×m\red{n \times m} 的方格图,每个方格中都有一个整数。

现有一只小熊,想从图的左上角走到右下角,每一步只能向上、向下或向右走一格,并且不能重复经过已经走过的方格,也不能走出边界。

小熊会取走所有经过的方格中的整数,求它能取到的整数之和的最大值。

输入格式

1\red 1 行两个正整数 n,m\red{n,m}

接下来 n\red{n} 行每行 m\red{m} 个整数,依次代表每个方格中的整数。

输出格式

一个整数,表示小熊能取到的整数之和的最大值。

样例

输入样例 1

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

输出样例 1

9

输入样例 2

2 5
-1 -1 -3 -2 -7
-2 -1 -4 -1 -2

输出样例 2

-10

样例解释 1

img

按上述走法,取到的数之和为1+2+(1)+4+3+2+(1)+(1)=9\red{1+2+(-1)+4+3+2+(-1)+(-1)=9},可以证明为最大值。

img

注意,上述走法是错误的,因为第2\red 2行第2\red 2列的方格走过了两次,而根据题意,不能重复经过已经走过的方格。

img

另外,上述走法也是错误的,因为没有右下角的终点。

样例解释 2

img

按上述走法,取到的数之和为(1)+(1)+(3)+(2)+(1)+(2)=10\red{(-1)+(-1)+(-3)+(-2)+(-1)+(-2)=-10},可以证明为最大值。因此,请注意,取到的数之和的最大值也可能是负数。

提示

对于 20%\red{20\%} 的数据,n,m5\red{n,m \le 5}

对于 40%\red{40\%} 的数据,n,m50\red{n,m \le 50}

对于 70%\red{70\%} 的数据,n,m300\red{n,m \le 300}

对于 100%\red{100\%} 的数据,1n,m1000\red{1 \le n,m \le 1000}。方格中整数的绝对值不超过 104\red{10^4}