喵星人的入侵

a180285幸运地被选作了地球到喵星球的留学生，其实是作为特工去调查喵星人是否有侵略地球的企图。喵星人果然打算入侵地球！从a180285口中得到确切消息之后，地球防御小组成员决定制定反侵略计划。
喵星到地球的一段必经之路可以看作 n*m的格点，喵星人将会从地图上的S位置出发，目的地是地球的入口T。为了抵抗喵星人的入侵，地球防御小组打算在地图的格点上放置一些炮塔（最多放置 K个），炮塔攻击周围的 8 个方向（8 个方向分别是：东，南，西，北，东北，西北，东南，西南）（如下左图所示，中间格子的炮塔可以攻击周围的八个格子）。此外地球防御小组还可以在地图上放置无限多个障碍，使得喵星人无法从有障碍的格子经过。

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

第一行为三个整数 n，m，K，分别表示地图的长和宽，以及最多能放置的炮塔数量。
接下来的n行，每行包含m个字符，‘#’表示地图上原有的障碍，‘.’表示该处为空地，数据保证在原地图上存在S 到T 的路径。

对于30%的数据，保证：
1<=N, M<=6

对于100%的数据，保证：
1<=N<=6
，
1<=M<=20

1<=K<=15

且从S 到T 的路径必定存在

输出在合理布阵下，喵星人采取最优策略后，会受到的最大伤害。
注意必须保证在布阵结束后喵星人仍然可以沿一条或以上的路径从起点S到达终点T，否则他们组织更大规模的侵略。

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

7