AT_joi2013yo_f お土産購入計画 (Gifts)

# 土特产购买计划 ## 题目背景 在澳大利亚旅游的JOI君将要回国。他现在所处的城市被划分为若干个区划，有道路、土特产店、住宅和国际机场。现在JOI君位于城市的西北角，将要前往位于城市东南角的国际机场。 JOI君每一次移动可以移动到相邻的区划，但不能进入有住宅的区划。为了赶上飞机，JOI君只能向西面或北面移动 $K$ 次。向东面和南面移动次数不限。 JOI君进入有土特产店的区划后购买土特产。经过调查，JOI君已经知道了去每个土特产店各可以买几个土特产。 求JOI君最多可以买到多少土特产。 购买土特产的时间可以忽略，如果多次前往同一家土特产店，只在第一次进入该店时购买土特产。

第 $1$ 行包含三个整数 $H$,$W$ 和 $K$。 接下来 $H$ 行，每行包含一个由 $W$ 个字符组成的字符串。其中，第 $i$ 行的第 $j$ 个字符 $(1≤i≤H，1≤j≤W)$ 表示从北向南第 $i$ 行，从西向东第 $j$ 列的区划信息。在信息中，道路由字符 `.` 表示，住宅区由字符 `#` 表示，土特产店由数字 $q$ $(1≤q≤9)$ 表示，$q$ 为进入该土特产店购买的土特产数量。位于东南角 $(H,W)$ 的国际机场也用字符 `.` 表示。

一个整数，表示JOI君可以购买的土特产数量的最大值。 ## 输入输出样例 #### 输入 #1 ``` 5 4 2 ...# .#.# .#73 8##. .... ``` #### 输出 #1 ``` 11 ``` ------------ #### 输入 #2 ``` 4 4 3 .8#9 9.#. .#9. .... ``` #### 输出 #2 ``` 27 ```

### 【解释-样例1】 在**输入/输出 #1**中，JOI君先向南移动3次，在位于 $(4,1)$ 的土特产店中购买了8个土特产。然后向南移动1次，向东移动3次，向北移动2次，在位于 $(3,4)$ 的土特产店中购买了3个土特产。最后向南移动2次到达国际机场。合计最多可购买11个土特产。 ### 【数据范围与约定】 对于 $100\%$ 的数据，$2≦H≦50$，$2≦W≦50$，$1≦K≦3$。 约定：对于每一组数据，JOI君的初始位置，即西北角 $(1，1)$ 均为道路。数据保证有解。 Translated by Georiky