Description

山洞的地图用一个 $R \times C$ 的字符矩阵表示：

• . 表示在开始的时候没有探险队员的空地，空地可以容纳任意多的探险队员；
• P表示在开始的时候有探险队员的空地，我们假设在开始的时候所有的队员都在不同的位置上，且没有队员恰好位于出口所在的方格；
• * 表示障碍物，探险队员不能经过被障碍物占据的方格；
• O（大写字母 O）表示出口，输入数据保证出口一定位于地图的边界上，即只有第 $1$ 行，第 $R$ 行，第 $1$ 列，第 $C$ 列有可能出现 O。

另外，输入数据保证整个地图被边界和出口围住，即第 $1$ 行，第 $R$ 行，第 $1$ 列，第 $C$ 列只能是 * 或 O。

Input Format

输入文件的第一行是用空格隔开的两个整数 $R$ 和 $C$，表示地图的大小。第二行是整数 $T$，即山洞将要坍塌的时间。接下来 $R$ 行，每行包含 $C$ 个字符，表示一幅山洞地图。

Output Format

输出一行，包含一个整数，即 $T$ 个单位时间内最多能逃出的人数。

5 5
4
*****
*P..*
O**.O
*P..*
*****

1

Hint

山洞有两个出口，但只有右边的出口是可以到达的。虽然在 $3$ 个单位时间内两人都可以到达出口左侧的方格处，但由于在出口处一个单位时间只能允许一人通过，故 $4$ 个单位时间内只能逃出一人。两人都逃出需要 $5$ 个单位时间。

• 对于 $30\%$ 的数据，队员数和出口数均不超过 $10$；
• 对于 $100\%$ 的数据，$3 \le R, C \le 12，0 < T \le 50$。