Steve是一名矿工，他热衷于挖掘矿石。

一天他来到了这片土地上，准备开采这里的矿产。他已经通过高(kai)科(wai)技(gua)手段了解到了这里的矿产分布，现在他想知道，在最多$T$个单位时间内，他能挖掘到的最大价值是多少？

Steve每个单位时间可以向左、右或下移动一格，并挖掘该格内的矿石。Steve不能向上移动、或是挖掘头顶的矿石。矿石不会被重复挖掘，意味着如果Steve经过一个格子多次，那么只有第一次经过可以获得相应价值的矿石。

输入格式

输入数据第一行为三个整数$n，m，T$，表示地图为$n$行$m$列，时间上限为$T$。

接下来$n$行，每行$m$个字符，含义如下：

• $0$（数字零）：表示该方格价值为$0$
• $1\cdots 9$：表示该方格的价值
• $P$：表示该方格为Steve的初始位置
• *：表示该方格不能被挖掘或行走

数据保证第$2$行由$m-1$个0和$1$个P组成，且第$3$至$n+1$行不会出现P。

输出格式

输出文件仅一行，一个整数，表示Steve在时限内能够获得的最大价值。

样例

样例输入

3 4 3
0P00
*663
*7**

样例输出

15

[样例解释]

如图，石头价值为$0$，金矿石价值为$6$，煤矿石价值为$3$，钻石矿石价值为$7$

第$1$个单位时间里，Steve可以向下挖掘并获得$6$点价值，他也可以选择向左或向右，但显然这两种方案并没有什么用。

第$2$个单位时间里，Steve可以向下挖掘并获得$7$点价值，总共$13$点；或者向右挖掘并获得$6$点价值，共$12$点。

第$3$个单位时间里，若Steve挖掘了矿石$6，7$，则他不能进行任何行动，总价值为$13$；

若Steve挖掘了矿石$6，6$，则他可以向右挖掘并获得$3$点价值，共$15$点。

总价值最大为15点。

数据范围与提示

• 对于$100$%的数据，$1 \leq n,m \leq 10 ，1 \leq T \leq 10$
• 时间限制：$1000\mathrm{ms}$
• 空间限制：$256000\mathrm{KB}$