问题文

JOI 王国有一片广阔的森林。森林呈长方形，被分割成南北 $H$ 格，东西 $W$ 格的方格状。在从北边数第 $i$ 格，西边数第 $j$ 格（$1 \leq i \leq H, 1 \leq j \leq W$）的区域里，生长着 $A_{i,j}$ 棵树。然而，在森林的西北角区域有一家木材加工工厂，该区域没有树生长。换句话说，$A_{1,1} = 0$。

人可以进入没有树生长的区域。并且，如果某个区域的东西南北相邻区域没有树生长，人可以移动到该区域。但是，人无法离开森林的范围。JOI君希望将木材砍伐，并且使森林的西北角区域和东南角区域之间可以互相通行。

木材砍伐的方式如下。首先，JOI君位于木材加工工厂所在的西北角区域。JOI君可以在当前所在的区域以及东西南北相邻的没有树生长的区域中以每分钟移动一次的速度移动。此外，JOI君可以在东西南北相邻的有树生长的区域中以每分钟砍伐一棵树。然而，当砍伐一棵树时，JOI君必须将砍伐的木材运送到西北角的木材加工工厂。JOI君在搬运木材的过程中的移动速度不变。在搬运木材的同时，JOI君无法砍伐其他树。

请求出满足条件的最小砍伐时间。这里所说的砍伐时间是指从最后一次砍伐树木到将其运送到木材加工工厂所需的时间。

制约条件

• $1 \leq H \leq 30$
• $1 \leq W \leq 30$
• $(H, W) \neq (1, 1)$
• $0 \leq A_{i,j} \leq 10000$ ($1 \leq i \leq H, 1 \leq j \leq W$)
• $A_{1,1} = 0$

输入

从标准输入中以以下格式输入。

$H$ $W$ $A_{1,1}$ $...$ $A_{1,W}$ : $A_{H,1}$ $...$ $A_{H,W}$

---

输出

以一行输出满足条件的最小砍伐时间。

小任务 1 [15分]

• $1 \leq H \leq 5$
• $1 \leq W \leq 5$

---

小任务 2 [28分]

• $A_{i,j} \leq A_{i,j+1}$ ($1 \leq i \leq H, 1 \leq j \leq W-1$)
• $A_{i,j} \leq A_{i+1,j}$ ($1 \leq i \leq H-1, 1 \leq j \leq W$)

---

小任务 3 [57分]

• 没有其他限制。

---

输入样例 1

2 3
0 1 2
3 4 5

输出样例 1

32

北边第 $i$ 格，西边第 $j$ 格的区域用 $(i, j)$ 表示。

首先砍伐 $(1, 2)$ 的树。这需要1分钟。

然后砍伐所有 $(1, 3)$ 的树。砍伐一棵树需1分钟，因此需要从 $(1,1)$ 往东移动1格，砍伐 $(1, 3)$ 的树，再往西移动1格回到 $(1,1)$。所以总共花费6分钟。

接下来砍伐所有 $(2, 3)$ 的树。砍伐一棵树需1分钟，因此需要从 $(1,1)$ 往东移动2格，砍伐 $(2, 3)$ 的树，再往西移动2格回到 $(1,1)$。所以总共需要25分钟。

总共用时 $1 + 6 + 25 = 32$ 分钟，因此输出为32。

---

输入样例 2

2 5
0 5 0 0 0
0 0 0 9 1

输出样例 2

13

只需砍伐 $(2, 5)$ 的树即可。

---

输入样例 3

2 5
0 2 0 0 0
0 0 0 9 1

输出样例 3

11

首先砍伐 $(1, 2)$ 的树，然后砍伐 $(2, 5)$ 的树。