[CSP-J 2020] 方格取数

题目描述

有一个 $n\times m$ 的方格图，每个方格中都有一个整数。现在有一只小熊想从左上角走到右下角，每一步只能向上、向下或向右走一格，并且不能重复经过已经走过的方格，也不能走出边界。

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

输入格式

第一行两个整数 $n,m$。

接下来 $n$ 行，每行 $m$ 个整数，依次表示每个方格中的整数。

输出格式

输出一个整数，表示小熊能取得的整数之和的最大值。

样例 #1

输入 #1

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

输出 #1

9

样例 #2

输入 #2

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

输出 #2

-10

数据范围与提示

样例 #1 中，一条最优路径取得的和为 $2+(-1)+4+3+2+(-1)+(-1)=9$。注意不能重复经过同一个方格，且路径必须到达右下角。

样例 #2 中，所有可行路径的和都为负数，答案也可能为负数。

数据范围与提示

• 对于 $20\%$ 的数据，$n,m \le 5$。
• 对于 $40\%$ 的数据，$n,m \le 50$。
• 对于 $70\%$ 的数据，$n,m \le 300$。
• 对于 $100\%$ 的数据，$1 \le n,m \le 10^3$，方格中整数的绝对值不超过 $10^4$。