题目背景

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

题目描述

城市里正在举行庙会。庙会里有很多摊位。庙会的会场是一个南北向H个摊位、东西向W个摊位组成的大型方阵。从北开始第i行、西开始第j列的一个摊位，我们表示为(i,j)。
正妹现在处于庙会的(1,1)位置，然后要往东或者往南走，一直走到(H,W)跟八尾勇汇合。(1,1)点和(H,W)和它们的东西南北邻近一个摊位都没有开张。别的地方也可能有一些摊位没有开张。
正妹是个吃货。只要到达一个摊位，总是经不起小吃的诱惑。如果这个摊位开张了，而且该摊位小吃还没有买过，就会买下这个摊位的小吃。无论这个摊位是否有开张，其东西南北直接相邻的摊位小吃的香味也很诱人，如果邻近的摊位的小吃没有买过，那么就在这些邻近（上下左右）的且没有买过的摊位（假设有r个）中，买其中的r-1个摊位的小吃。然后继续往东或者南走。同一家小摊，不会购买多次。
虽然正妹是个吃货，但是零用钱还是很有限。可是她又是管不住自己，就是要买买买。所以她希望知道自己最少能吃掉多少钱的东西。

输入格式：

第一行2个数，H，W
接下来H行，每行W个字符串，没有空格隔开，是1-9或者'.'中的一个，表示价格，一个点表示没有开张。

输出格式：

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

输入样例#1：

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

输出样例#1：

9