配点: 100 点
問題
JOI 您居住的IOI市位于南北方向。 H 剖面,东西方向 W 它具有矩形形状, 它分为H \times W 部分。从北方 i ,从西边 j 第分区 表示为 (i, j) 。目前,IOI 城正在举办一场大型庆典,以纪念正在举办的国际编程大赛。有些区域设有摊位,每个摊位都出售不同类型的糖果。隔间 (1, 1),区画 (H, W) 及其邻近的北、南、东、西区域没有小吃摊。
JOI你是一段 从 (1, 1) 分区 移至 (H, W) 。为了缩短旅行时间,JOI只向东或向南移动。 JOI 你喜欢甜食,所以每次进入车厢时,你都会按顺序进行以下动作。
- 如果当前区域有卖糖果的摊位,而您还没有购买过,请在该摊位购买糖果。
- 如果在与北、南、东、西以及当前区域相邻的区域中有出售您尚未购买的糖果的摊位,则这些摊位中 1 致电除一个摊位外的所有摊位的销售人员并购买糖果。
JOI 你不会多次购买同一种糖果。
IOI 鉴于城市的规模、摊位的位置以及每个摊位的糖果价格,JOI 求前往 (1, 1) 分区 移至 (H, W) 旅行时购买糖果的最低总量。 由
入力
输入是 有一条 1 + H 行组成。 在
1 行中,2 整数 H, W (3 \leqq H \leqq 1\,000,3 \leqq W \leqq 1\,000)以空格作为分隔符。这是因为IOI城 表示它分为 H \times W 部分。
续 H 每行有 W 写入一串字符,代表IOI城各个部分的信息。H 行 i 从该行的左侧开始 j 第一个字符 (1 \leqq i \leqq H,1 \leqq j \leqq W) 是一个分区
如果 (i, j) 中没有停顿 . (句号)。如果有摊位 1, 2, \ldots, 9 代表该摊位出售的糖果的价格。
给出 5 在输入数据中,输入 1 ,档位数量为 20 下面。
出力
JOI 口交 (1, 1) 分区 移至 (H, W) 旅行时购买糖果的最低总量 输出为 1 行。 在
入力例 1
5 5 ..483 .59.9 3.866 79... 4.8..
出力例 1
20
入出力例 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) 摊位出售的糖果,则您购买的糖果总量将为最少。
入力例 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