测试数据来自 zzjOJ/64a669781365a155a1fa9906

题目背景

Steve在MC里是一名矿工，他热衷于挖掘矿石。他已经通过高科技手段了解到了这里的矿产分布地图。

题目描述

既然有了地图，那就不能浪费吧。。。现在他想知道，在最多 T 个单位时间内，他能挖掘到的最大价值是多少？
1）Steve每个单位时间可以向左、右或下移动一格，并挖掘该格内的矿石。
2）Steve不能向上移动、或是挖掘头顶的矿石。
3）矿石不会被重复挖掘，意味着如果Steve经过一个格子多次，那么只有第一次经过可以获得相应价值的矿石。

输入格式

输入数据第一行为三个整数 \(n\),\(m\),\(T\) ，表示地图为 \(n\)行 \(m\) 列，时间上限为 \(T\)。
接下来 \(n\) 行，每行 \(m\) 个字符，含义如下：
0~9表示这个位置的价值。
* 表示这个位置不能行走。
P 表示Steve在这里。
数据保证2~n+1行只出现1次P。

样例输入

3 4 3
0P00
*663
*7**

样例输出

15