问题

JOI 君所居住的 IOI 市，呈南北方向有 $H$ 个区块，东西方向有 $W$ 个区块，形状为长方形，拥有 $H \times W$ 个区块。从北向南数第 $i$ 个区块，从西向东数第 $j$ 个区块，记为 $(i, j)$。现在，为了纪念在 IOI 市正在举办的国际程序设计竞赛，一场大规模的庆祝活动正在进行中。有一些区块摆放了摊位，并且每个摊位上销售不同种类的糖果。区块 $(1, 1)$、区块 $(H, W)$ 以及与它们相邻的东、西、南、北方向上的区块没有摊位。

JOI 君要从区块 $(1, 1)$ 移动到区块 $(H, W)$。为了尽可能缩短移动时间，JOI 君只能向东或向南移动。由于 JOI 君喜欢糖果，所以每进入一个区块，他会按顺序执行以下操作：

• 如果当前区块上有还未购买的糖果摊位，他会在该摊位购买糖果。
• 如果当前区块东、西、南、北方向上的相邻区块有还未购买的糖果摊位，他会从这些摊位中选择一个（除去其中一个）并召唤售货员购买糖果。

JOI 君不会重复购买同一种糖果。

给定 IOI 市的大小、摊位位置以及每个摊位上糖果的价格，请计算出 JOI 君在从区块 $(1, 1)$ 移动到区块 $(H, W)$ 的过程中，所购买的糖果的总价的最小值。

输入

输入共有 $1 + H$ 行。

第一行包含两个整数 $H, W$ ($3 \leq H \leq 1,000$，$3 \leq W \leq 1,000$)，两个整数之间用一个空格分隔。表示 IOI 市被分割为 $H \times W$ 个区块。

接下来的 $H$ 行，每行包含有 $W$ 个字符，表示 IOI 市中每个区块的信息。对于第 $i$ 行中从左至右的第 $j$ 个字符（$1 \leq i \leq H$，$1 \leq j \leq W$），如果该区块上没有摊位，则用 . 表示；如果该区块上摆放了摊位，则用 1、2、$\ldots$、9 中的一个数字表示，代表该摊位上糖果的价格。

在所给入力数据中，对于输入 $1$，区块上摆放的摊位数量不超过 $20$。

输出

请以一行输出 JOI 君在从区块 $(1, 1)$ 移动到区块 $(H, W)$ 的过程中，所购买的糖果的总价的最小值。

输入样例 1

5 5
..483
.59.9
3.866
79...
4.8..

输出样例 1

20

在样例输入 1 中，JOI 君按照以下顺序移动：区块 $(1, 1)$、区块 $(2, 1)$、区块 $(3, 1)$、区块 $(3, 2)$、区块 $(4, 2)$、区块 $(4, 3)$、区块 $(4, 4)$、区块 $(4, 5)$、区块 $(5, 5)$。他会在区块 $(3, 1)$、区块 $(3, 3)$、区块 $(4, 2)$ 出摊位上购买糖果，这样购买糖果的总价最小。

输入样例 2

12 10
..498522.4
.633527629
54.4621596
634.213458
1924518685
7739539767
276155.3.6
87716372.2
.858877595
7998739511
3438.5852.
568.9319..

输出样例 2

63