题目背景

一批探险队员正在一个迷宫一样的山洞里摸索，突然他们得到了一个糟糕的消息，由于附近发生地震，这个山洞将有可能在 $T$ 个单位时间后坍塌。现在他们要用最快的速度找出一个方案，使得在 $T$ 个单位时间内逃出的队员最多。已知探险队员在一个单位时间内可以向前后左右任一方向移动一格，也可以停留在原地不动。有一个糟糕的情况是，虽然山洞的内部比较宽敞，但山洞的出口都非常狭窄，一个单位时间只能允许一名队员通过。

题目描述

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

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

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

输入格式

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

输出格式

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

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

1

提示

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

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