题目描述

给定一张 $n$ 行 $m$ 列的地图。Lucy 从字符 P 所在的格子出发，每个单位时间可以向上、下、左、右移动一格。她不能经过障碍物，也不能重复到达同一个格子。

地图中的数字字符表示该格子中遗物的价值，字符 0 表示价值为 $0$，字符 * 表示障碍物。到达一个数字格子时，可以获得该格子的价值。

Lucy 最多移动 $T$ 次。请计算她能够获得的最大总价值。她可以在不足 $T$ 次移动时停止。

输入格式

第一行包含三个整数 $n,m,T$。

接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串，表示地图。地图中恰好有一个字符 P。

输出格式

输出一个整数，表示能够获得的最大总价值。

3 4 3
0P00
*663
*7**

15

数据范围与提示

• $2 \le n,m \le 9$
• $2 \le T \le 9$