小红的rpg游戏
题号：NC229960
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小红正在玩一个游戏。游戏的地图是一个n*m的迷宫，迷宫有墙和道路，道路上可能会有一些怪物。
小红初始的血量是 h ，每当小红经过一个有怪物的道路时，小红就会和怪物战斗，击杀怪物并且消耗自己的血量。小红消耗的血量等同于该怪物的战斗力。请注意，如果小红血量为0则死亡。因此只有当小红当前血量大于怪物的战斗力时才可经过该点。
地图共有以下几种标识：
'.' 代表道路，小红可以经过。
'*' 代表墙体，小红不能经过。
'1'~'9' 数字，代表该位置是个道路，且上面有一个战斗力为该数字的怪物。
小红只可以上下左右四个方向移动。
小红想知道，自己从左上角到右下角的最短行走路线的距离是多少？

输入描述:

第一行三个正整数 n 、m 和 h ，用空格隔开。
接下来的 n 行，每行一个长度为 m 的字符串，用来表示地图。保证输入是合法的。
数据范围：
，且怪物的数量不超过10个。保证左上角和右下角都是道路且没有怪物。

输出描述:

如果小红无法到达右下角，则输出-1。否则输出一个正整数，代表小红走的路径长度最小值。
示例1

输入

复制 
3 3 3
.11
.*.
22.

输出

复制 
4

说明

小红先向右走两步，再向下走两步，可到达右下角。中途击杀两只战斗力为1的怪物，剩余血量为1。若小红先向下走，则无法击杀两只血量为2的怪物，无法到达终点。
示例2

输入

复制 
3 3 3
.12
.*.
21.

输出

复制 
-1