题目背景

伟大昊天金阙无上至尊自然妙有弥罗至真玄穹高上无敌暴龙战士盾构大王数值怪胖头鱼大帝王嘉逸幸运地被选作了地球到91星球的留学生，其实是作为特工去调查，胖头鱼星人是否有侵略地球的企图。胖头鱼星人果然打算入侵地球！从王嘉逸口中得到确切消息之后，地球小组成员决定制定反侵略计划。

题目描述

胖头鱼星到地球的一段必经之路可以看作 $n×m$ 的格点，胖头鱼星人将会从地图上的 $S$ 位置出发，目的地是地球的入口 $T$。

为了抵抗胖头鱼星人的入侵，地球防御小组打算在地图上的格点上放置一些炮塔（最多放置 $K$ 个），炮塔攻击周围的 $8$ 个方向（分别是：东、南、西、北、东北、西北、东南、西南）。此外地球防御小组还可以在地图上放置无限多个障碍，使得胖头鱼星人无法从有障碍的格子经过。

作为地球防御小组的特工，请你为胖头鱼星人布阵，使得胖头鱼星人受到的伤害最大。注意如果有多条从 $S$ 到 $T$ 的路径，胖头鱼星人会选择伤害最小的一条。

输入格式

第一行为三个整数 $n,m,K$，分别表示地图的长和宽，以及最多能放置的炮塔数量。

接下来的 $n$ 行，每行包含 $m$ 个字符，# 表示地图上原有的障碍，. 表示该处为空地，数据保证在原地图上存在 $S$ 到 $T$ 的路径。

输出格式

输出在合理布阵下，胖头鱼星人采取最优策略后，会受到的最大伤害。

注意必须保证在布阵结束后胖头鱼星人仍然可以沿一条或以上的路径从起点 $S$ 到达终点 $T$，否则他们组织更大规模的侵略。

输入输出样例 #1

输入 #1

3 3 1
S.T
...
...

输出 #1

7

说明/提示

数据范围及约定

对于 100% 的数据，保证 $min(n,m)≤6，max(n,m)≤20，1≤K≤15$ ，且从 $S$ 到 $T$ 的路径必定存在。