当前没有测试数据。

题目描述

$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

数据范围

对于 $100\%$ 的数据，满足 $1 < n, m < 10$，$1 < T < 10$。