土特产购买计划

题目背景

在澳大利亚旅游的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