Lucy 是一名勇敢的探险家，她热衷于探索未知的领域。最近，她听说了一个神秘的遗迹，据说那里隐藏着无尽的宝藏。决心一探究竟，Lucy 踏上了前往这个神秘遗迹的旅程。
她来到了一个名叫阿尔卡迪亚的地方，准备探索那里的秘密。通过研究，Lucy 了解到了阿尔卡迪亚的地图和一些重要的信息。
已知，Lucy 每个单位时间可以向 上、下、左、右 移动一格，并且她可以在每个格子中发现遗物。然而，有些格子可能是空的，没有任何价值。
另外，遗物不会被重复发现，这意味着如果 Lucy 经过一个格子之后，就不会重复的再走到这个格子中了。
现在，她想知道在规定的时间 T 内，她能够发现遗物的最大总价值是多少？
输入数据的第一行包含三个整数 n，m，T，分别表示地图的行数、列数，以及给定的时间上限。
接下来的 n 行，每行包含 m 个字符，具体含义如下：
0：表示一个空格子，没有任何价值的遗物。
1...9：表示一个有价值的遗物，其价值为 1 到 9 之间的整数。
P：表示 Lucy 的初始位置。
*：表示一个不可通过的障碍物。
需要注意的是:
第二行由 m-1 个 0 和 1 个 P 组成。
第三行到第 n+1 行不会出现 P。
输出文件仅一行，一个整数，表示 Lucy 在时限内能够获得的最大总价值。
3 4 3 0P00 *663 *7**
15
2 3 1 0P0 1*2
0
8 4 8 0P00 1*49 3*78 *567 **9* **86 3*** 2*37
51
第 1 个单位时间里，Lucy 可以向下挖掘并获得 6 点价值，他也可以选择向左或向右，但显然这两种方案并没有什么用。
第 2 个单位时间里，Lucy 可以向下挖掘并获得 7 点价值，总共 13 点，或者向右挖掘并获得 6 点价值，共 12 点。
第 3 个单位时间里，若 Lucy 已经挖掘了遗物 6，7，则他不可能再挖掘到其他遗物，获得遗物总价值为 13。 若 Lucy 已经挖掘了遗物 6，6，则他可以向右挖掘并获得 3 点价值，获得遗物总价值为 15 点。
因此，得到遗物总价值最大为 15 点。
对于 100\% 的数据，满足 1 \lt n,m \lt 10 ， 1 \lt T \lt 10。