现在你是一名消防队长。这不是一份轻松的工作。你拥有一个建筑物内房间的平面布局，表现为一个二维网格。已知人们将占据的位置、人们无法进入或离开的位置，以及出口的位置。你知道在同一时间，两个或更多的人不能占据二维网格中的同一个单元格。你知道每个人需要在多少秒内撤离房间。假设居住者只能沿四个基本方向（即北、南、东或西）移动，并且每秒可以移动一步。你可以假设虽然出口处一次只能站一个人，但处于出口处的人是安全的，当然，任何通过出口的人也是安全的。

给定房间的布局和期望的撤离时间，确定有多少人可以安全撤离。

输入格式

输入的第一行包含三个整数 $n, m$ ($1 \le n, m \le 20$) 和 $t$ ($1 \le t \le 200$)，其中 $n$ 和 $m$ 是楼层平面图的高度和宽度，$t$ 是允许撤离的时间。

接下来的 $n$ 行，每行包含一个长度恰好为 $m$ 的字符串，仅由字符 “P”、“E”、“#” 和/或 “.” 组成，其中：

• “P” 代表一个人
• “E” 代表一个出口
• “#” 代表人们无法进入或通过的封闭区域
• “.” 代表人们可以进入和通过的开放区域

输出格式

输出一个整数，表示在规定时间内可以安全撤离的房间居住者人数。

样例

样例输入 1

4 5 3
.....
..P#.
..PPE
..P.E

样例输出 1

4

样例输入 2

3 3 5
...
P#P
P#E

样例输出 2

2