AT_s8pc_3_d お土産購入計画2

# 纪念品购买计划 ## 题目背景 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