题目背景

本题时限 3s，请考虑常数优化或者读入优化。（std 没有特别进行优化）

题目描述

城市里正在举行庙会。庙会里有很多摊位。庙会的会场是一个南北向 $H$ 个摊位、东西向 $W$ 个摊位组成的大型方阵。从北开始第 $i$ 行、西开始第 $j$ 列的一个摊位，我们表示为 $(i,j)$。

正妹现在处于庙会的 $(1,1)$ 位置，然后要往东或者往南走，一直走到 $(H,W)$ 跟小 B 汇合。$(1,1)$ 点、$(H,W)$ 点和它们的东西南北邻近一个摊位都没有开张。别的地方也可能有一些摊位没有开张。

正妹是个吃货。只要到达一个摊位，总是经不起小吃的诱惑。如果这个摊位开张了，而且该摊位小吃还没有买过，就会买下这个摊位的小吃。无论这个摊位是否有开张，其东西南北直接相邻的摊位小吃的香味也很诱人，如果邻近的摊位的小吃没有买过，那么就在这些邻近（上下左右）的且没有买过的摊位（假设有 $r$ 个）中，买其中的 $r-1$ 个摊位的小吃。然后继续往东或者南走。同一家小摊，不会购买多次。

虽然正妹是个吃货，但是零用钱还是很有限。可是她又是管不住自己，就是要买买买。所以她希望知道自己最少能吃掉多少钱的东西。

输入格式

第一行两个整数 $H$ 和 $W$。

接下来 $H$ 行，每行一个长度为 $W$ 的字符串，没有空格隔开，是 $1\sim9$ 或者 . 中的一个，数字表示价格，. 表示没有开张。

输出格式

一个整数，表示最少花掉的钱。

5 5
....7
.21.8
9346.
..45.
.8...

9

提示

5 5
oooo7
.2xoo
9346o
..45o
.8..o

样例解释：o 为正妹经过的路线，x 为她顺便买的小吃。当走到 $(2,4)$ 时，左下右都有开张且没有买过的摊位，于是买左和右，继续沿着路线走。由于之后路线没有经过没有买过摊位，而且上下左右开张且没买过的摊位不超过 $1$，所以一个都不买了。

对于 $20\%$ 的数据，开张的摊位不超过 $20$；

对于 $100\%$ 的数据，保证 $3\le H,W\le1000$。

特别注意：数据是在 Windows 生成，输入数据换行符可能是 \r\n（两个字符）或者 \n。而评测机是 Linux。请特别注意。不接受赛后以「本地能过，评测 WA」的理由申诉。

参考读入方式（节选自 std）：

for (i = 0; i < H; ++i) {
	scanf("%s", in);
	for (j = 0; j < W; ++j) {
		shop[i][j] = blabla..
	}
}