AT_joi2016yo_f 屋台 (Food stalls)

JOI君居住的IOI市南北方向为 $H$ 区域，东西方向为 $W$ 区域的长方形形状，被划分为 $H×W$ 个区域。从北到第 $i$ 个区域，从西到第 $j$ 个区域表示为$(i，j)$现在，为了纪念在IOI市举办的国际编程比赛，举办了大规模的节日活动。几个区域里出现了小摊，各自销售不同种类的点心。从区域$(1，1)$，到区域$(H，W)$ 以及南北方向的摊位。 JOI君从区域 $(1，1)$ 移动到区域$(H，W)$。为了缩短移动时间，JOI君只向东或南移动。JOI君喜欢点心，所以每次进入区域都会依次采取以下行动。 - 现区域若有摊贩出售未购买的糕点，则在该摊贩购买糕点。 - 现在区域的东西南北邻接区划出现了卖还没有买的点心的摊位时，从这些摊位中除了一个以外的所有摊位有销售员，购买点心。 JOI君不会多次购买同一种类的点心。 给你IOI市的大小、摊位的位置和各个摊位的点心价格，求出JOI君从区域 $(1，1)$ 移动到区划 $(H，W)$ 期间购买的点心总额的最小值。

一共有$H + 1$行。 在第$1$行中，有$2$个整数$H,W(3\le{H}\le{1000}),(3\le{W}\le{1000})$，中间以空白作为分隔符写着，这表示IOI市被划分为 $H×W $个区域。 接下来的 $H$ 行分别写有由 $W$ 个字符组成的字符串，表示IOI市各个区域的信息。$H$行中从第$i$行的左边数第$j$个字符，在区域$(i，j)$中没有摊位的情况下。（句号）。有摊位时为$1,2,……,9$中的任意一种，表示该摊位销售的点心的价格 在给出的$5$个输入数据中，在输入$1$中，摊位所在区域的数量为$20$以下。

共一行，JOI君从区域 $(1，1)$ 移动到区域 $(H，W)$ 期间，购买的点心总额的最小值。

### Sample Explanation 1 入出力例 $ 1 $ においては，区画 $ (1,\ 1) $，区画 $ (2,\ 1) $，区画 $ (3,\ 1) $，区画 $ (3,\ 2) $，区画 $ (4,\ 2) $，区画 $ (4,\ 3) $，区画 $ (4,\ 4) $，区画 $ (4,\ 5) $，区画 $ (5,\ 5) $ の順番に移動して，区画 $ (3,\ 1) $，区画 $ (3,\ 3) $，区画 $ (4,\ 2) $ の屋台で販売しているお菓子を購入すると，購入するお菓子の総額が最小となる． - - - - - -