背景

翻译自 NordicOI 2024 C。

题目描述

Uolevi 在一个冻湖上，湖可以被分为 $n\times m$ 的网格，每个格子上都有一个金币。

每个格子有一个承受能力，即这个格子的冰上能承受的最大金币数量。

每一步，Uolevi 可以向上、下、左或右移动一格，但不能超出 $n\times m$ 的边界。如果 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 不可能收集到大于等于 $6$ 个金币，因为边缘所有格子的承受能力都小于等于 $5$。

数据范围：

本题采用捆绑测试。