问题

JOI君来到了澳大利亚旅行，在各种地方游览，终于到了回国的日子。现在，JOI君在离开的那个国际机场所在的城市。这个城市被划分为东西南北四个区块，每个区块都有道路、纪念品店、住宅和国际机场。JOI君从最北西的区块出发，目标是最南东的区块的国际机场。

JOI君可以从当前区块移动到相邻的区块，但不能进入住宅区块。另外，为了赶上飞机的时间，只能向东或向南移动。然而，由于时间还有一些余地，JOI君可以在当前区块向北或向西移动最多$K$次。

当JOI君进入纪念品店时，他会为了日本的朋友们买纪念品。由于JOI君对纪念品店进行了详细调查，所以知道在哪家纪念品店购买可以买到多少个纪念品。请编写一个程序来计算JOI君能购买的纪念品的最大数量。

但是，请忽略购买纪念品所花费的时间，当JOI君多次访问同一家纪念品店时，只在第一次访问时购买纪念品。

输入

输入由 $1 + H$ 行组成。

第 1 行包含三个整数 $H, W, K$ ($2 \leqq H \leqq 50$，$2 \leqq W \leqq 50, 1 \leqq K \leqq 3$) ，以空格分隔。

接下来的 $H$ 行，每行包含 $W$ 个字符，代表区块的信息。第 $i$ 行第 $j$ 个字符表示区块 $(i, j)$ 是道路还是国际机场，用'.'表示，是住宅用 '#' 表示。如果是纪念品店，则用 '1'、'2'、...、'9' 中的一个字符表示，其值对应该纪念品店能够买到的纪念品的数量。

在所给的输入数据中，保证JOI君最初所处的最北西的区块是道路。 JOI君能够到达国际机场也是保证的。

输出

输出一个整数，表示JOI君可以购买的纪念品的最大数量。

示例输入1

5 4 2
...#
.#.#
.#73
8##.
....

示例输出1

11

在输入示例1中，JOI君向南移动3次到达区块$(4, 1)$的纪念品店购买商品，然后再向南移动1次，向东移动3次，然后向北移动2次到达区块$(3, 4)$的纪念品店购买商品。最后向南移动2次到达国际机场，总共能够购买11个纪念品。

示例输入2

4 4 3
.8#9
9.#.
.#9.
....

示例输出2

27