题目描述

题目译自 NordicOI 2024 T3 「Thin Ice」

Uolevi 站在一个 $n \times m$ 网格形状的冰冻湖上，每个方格上都有一个硬币。

每个方格都有一个耐久度，即方格上能承受的硬币数量。

在一步中，Uolevi 可以向上、向下、向左或向右移动一个方格，但不能超出湖的边界。如果 Uolevi 当前所在的方格上有硬币，他可以捡起来。

当 Uolevi 移动到一个方格时，方格上的硬币数量永远不能超过方格的耐久度。这包括 Uolevi 携带的硬币，以及如果还没有被捡起来的冰上的硬币。Uolevi 自己的重量可以忽略不计。

Uolevi 想进行一次起点和终点都是边缘方格的旅行。他旅行期间能收集到的最大硬币数量是多少？

输入格式

输入的第一行包含整数 $n$ 和 $m$，分别表示湖的高度和宽度。

接下来的 $n$ 行，每行有 $m$ 个整数，分别表示每个方格上冰的耐久度 $d$。

输出格式

输出 Uolevi 可以收集到的最大硬币数量。

3 4
1 1 1 1
1 3 6 1
3 4 5 1

5

Uolevi 可以从左上角开始，按照以下方式移动：

向下 $\rightarrow$ 捡硬币 $\rightarrow$ 向右 $\rightarrow$ 捡硬币 $\rightarrow$ 向下 $\rightarrow$ 向左 $\rightarrow$ 捡硬币 $\rightarrow$ 向右 $\rightarrow$ 捡硬币 $\rightarrow$ 向右 $\rightarrow$ 捡硬币

请注意，Uolevi 不能收集六个硬币，因为这样做他将无法回到边缘方格。

数据范围与提示

详细子任务附加限制及分值如下表所示。