当前没有测试数据。

题目描述

公主被魔王抓起来关在了迷宫的某处，骑士想要拯救公主，也进入了迷宫。但是魔王不会轻易让骑士拯救公主，魔王在迷宫中安排了许多怪兽。每个怪兽都有血量，骑士也有初始血量，骑士打败怪兽后血量的减少量为怪物的血量值，血量减到 $0$，骑士会死去。

迷宫由 $m\sim n$ 个方块组成，每个方块有墙或者路或者怪物，骑士在其中一个方块上，他每个时间单位可以四个方向（上、下、左、右）走到相邻方格，若遇到怪物，必须打败怪物才能继续前进。请帮忙判断骑士能否成功拯救公主，如果能，给出骑士还剩的最大血量。

输入格式

第一行为三个整数 $m$、$n$ 和 $t$，$t$ 表示骑士的初始血量，$m,n \le 20, t \le 30$。

第 $2$ 至 $m+1$ 行描述了迷宫，迷宫以 $m$ 行 $n$ 列的方格组成，若方格为 . 则表示骑士可以通过，若方格为 # 则表示墙，骑士不能通过，若方格为数字则表示怪物，数字为怪物的血量，保证怪物的血量小于 $10$（一位数）。* 表示了骑士当前所在的位置，+ 表示公主被囚禁的位置。

输出格式

若骑士能成功拯救公主，则输出骑士走到公主所囚禁方格所剩最大血量，否则输出 $0$。

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

4