AT_joi2018_yo_e.森林伐採（Deforestation）

JOI 王国有一片广阔的森林，这片森林呈矩形，被划分为 $H$ 行 $W$ 列的格子。位于第 $i$ 行第 $j$ 列（$1 \leq i \leq H, 1 \leq j \leq W$）的格子中，有 $A_{i,j}$ 棵树。特别地，森林的西北角有一个木材加工厂，没有树木，即 $A_{1,1}=0$。

没有树的区域是可以进入的。人可以从当前所在位置，向东、西、南、北方向移动到相邻的没有树木的格子。只能在森林内活动，不能走出森林。JOI 君想通过伐木，开辟一条通道，使得可以在西北角和东南角的区域之间自由来去。

伐木时，JOI 君最初位于西北角的木材加工厂。他能在 $1$ 分钟内移动到相邻的无树区域。另外，他可以在 $1$ 分钟内砍伐相邻有树区域中的一棵树。每砍下树，就必须返回西北角的木材加工厂运送这段树木。在运送过程中，JOI 君的移动速度保持不变，而且在此期间无法砍伐其他树木。

请计算完成连接西北至东南通道所需的最短时间。这里的伐木时间是指最后一次砍下的树木被运回木材加工厂的时间。

从标准输入中读入数据，格式如下：

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

输出满足条件的最小伐木时间。

条件

• $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$

子任务 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

用 $(i, j)$ 表示第 $i$ 行第 $j$ 列的区域。首先，砍倒 $(1, 2)$ 位置的树，需要 $1$ 分钟。接着，砍掉 $(1, 3)$ 的所有树。每砍一棵树，从 $(1, 1)$ 出发往东走 $1$ 步到 $(1, 3)$ 进行砍伐，再折返回 $(1, 1)$，花费 $3$ 分钟，总共 $6$ 分钟。随后，前往 $(2, 3)$ 砍树，每棵树要花 $5$ 分钟（从 $(1, 1)$ 向东走 $2$ 步到 $(2, 3)$ 砍完树，再向西走 $2$ 步返回），总共 $25$ 分钟。因此，最短伐木时间为 $1 + 6 + 25 = 32$ 分钟。这是无法减少的时间，所以输出 $32$。

样例解释 2

只需砍掉在 $(2, 5)$ 的树。

样例解释 3

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

本翻译由 AI 自动生成