题目描述

公主被魔王抓起来关在了迷宫的某处，骑士想要拯救公主，也进入了迷宫。 魔王在迷宫中安排了许多怪兽，每个怪兽都有血量，骑士也有初始血量，骑士打败怪兽后血量的减少量为怪物的血量值，血量减到0骑士会死去。 迷宫由m*n个方块组成，每个方块有墙、路或者怪物，骑士初始在其中一个方块上，每个时间单位可以向上下左右四个方向走到相邻方格，若遇到怪物必须打败怪物才能继续前进。 请判断骑士能否成功拯救公主，如果能，给出骑士还剩的最大血量。 时间限制：1000ms 内存限制：65536KB

输入说明

第一行为三个整数m、n和t，t表示骑士的初始血量。(m,n <= 20, t <= 30) 第2至m+1行描述迷宫，迷宫为m行n列的方格，各标识含义如下：

• .：表示可通行的路
• #：表示墙，骑士无法通行
• 数字：表示怪物，数字值为怪物的血量（均为小于10的一位数）
• *：表示骑士的初始位置
• +：表示公主的囚禁位置

输出说明

若骑士能成功拯救公主，输出走到公主位置时的剩余最大血量，否则输出0。

样例输入

5 6 10
..*...
.#2###
5#..4#
.##9.#
.#+..#

样例输出

4