题目描述

E869120とsquare1001は, $H\ \times\ W$ のマス目を移動して, お土産を買うことにしました。
左上のマスがスタート地点, 右下のマスがゴール地点です。
上から$i$番目, 左から$j$番目には, $a_{i,\ j}$ 個のお土産が売られています。
そこで, 2人で協力してお土産をできるだけ多く集めることにしました。
しかし, 2人は最短経路で行かなければなりません。そうしないとTLEします。
そのとき, 買うことができるお土産の個数の最大値を求めなさい。

输入格式

入力は以下の形式で標準入力から与えられる。

$H\ W$ $a_{1,\ 1}\ a_{1,\ 2}\ \cdots\ a_{1,\ W}$ $a_{2,\ 1}\ a_{2,\ 2}\ \cdots\ a_{2,\ W}$ $\vdots\ \vdots\ \vdots$ $a_{H,\ 1}\ a_{H,\ 2}\ \cdots\ a_{H,\ W}$

• $1$行目に, 整数$H$と$W$が与えられる。
• $2$行目から$H+1$行目には, $W$個の整数が空白区切りで与えられる。

输出格式

出力は以下の形式で標準出力に従うこと。

• 買うことのできるお土産の個数の最大値を1行に出力しなさい。

题目大意

纪念品购买计划

题目背景

Sigma和他的兄弟Sugim正在 $H×W$ 的网格中。他们想要买一些纪念品。

题目描述

为了得到尽可能多的纪念品，他们决定各自行动出发购买。

他们的初始位置是网格的左上角，目的地是右下角。在一些格子中有纪念品商店。在第 $i$ 行和第 $j$ 列的格子有 $a_{i,j}$ 个纪念品。

每一次移动，他们都可以走进上、下、左、右任一方向的相邻格子。但由于时间紧迫，他们只能走 $H+W-2$ 次。

求他们两人最多一共能买多少个纪念品。

注意：某一格的纪念品只能被购买1次，即使一个人或两个人多次进入该格。详见 【解释-样例1】

输入格式

第 $1$ 行包含 $2$ 个整数 $H,W$。

接下来 $H$ 行，每行 $W$ 个整数，用空格分开。

输出格式

一个整数，表示他们合计能买到的纪念品数量的最大值。

输入输出样例

输入 #1

3 3
1 0 5
2 2 3
4 2 4

输出 #1

21

---

输入 #2

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

输出 #2

97

说明/提示

【解释-样例1】

在输入/输出#1中，他们的路径可以是：

Sigma: $(1,1)->(1,2)->(1,3)->(2,3)->(3,3)$。

Sugim: $(1,1)->(2,1)->(3,1)->(3,2)->(3,3)$。

于是得到21个纪念品。

注：两人都进入过 $(1,1)$ 与 $(3,3)$ ，但每格都只被购买了 $1$ 次。

【数据范围与约定】

对于 $100\%$ 的数据，$1≤H,W≤200$，$0≤a_{i,j}≤10^5$。

【计分规则】

本题满分 $600$ 分。 | $Subtask$ | 分值 | 特殊限制 | | :----------: | :----------: | :----------: | | $Subtask 1$ | 50 | $1≤H≤2$ | | $Subtask 2$ | 80 | $1≤H≤3$ | | $Subtask 3$ | 120 | $1≤H,W≤7$ | | $Subtask 4$ | 150 | $1≤H,W≤30$ | | $Subtask 5$ | 200 | 无 |

Translated by Georiky

3 3
1 0 5
2 2 3
4 2 4

21

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

97

提示

制約

• $1\ \le\ H,\ W\ \le\ 200$
• $0\ \le\ a_{i,\ j}\ \le\ 10^5$

小課題

小課題1 [50点]

• $1\ \le\ H\ \le\ 2$ を満たす。

小課題2 [80点]

• $1\ \le\ H\ \le\ 3$ を満たす。

小課題3 [120点]

• $1\ \le\ H,\ W\ \le\ 7$ を満たす。

小課題4 [150点]

• $1\ \le\ H,\ W\ \le\ 30$ を満たす。

小課題5 [200点]

• 追加の制約はない。

Sample Explanation 1

ここでは, 上から $i$ 番目, 左から $j$ 番目を $(i,\ j)$ とします。 そのとき, 次のような進み方が最適です。 - E869120は, $ (1,\ 1)\ -\ >\ (1,\ 2)\ -\ >\ (1,\ 3)\ -\ >\ (2,\ 3)\ -\ >\ (3,\ 3) $ と進む。 - square1001は, $ (1,\ 1)\ -\ >\ (2,\ 1)\ -\ >\ (3,\ 1)\ -\ >\ (3,\ 2)\ -\ >\ (3,\ 3) $ と進む。 また, 2人は合計で21個のお土産を買うことができます。