You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述：

AC君是一个游戏关卡策划，他正在设计一个迷宫

迷宫有N行M列，其中每个位置是平地或障碍物，另外有两个位置作为起点和终点，也视为平地。

玩家将从起点出发，在T秒内到达终点。每次可以从当前位置移动到上下左右相邻的其他格。如果移动目的地是空地的话需要1秒，如果是障碍物的话需要x秒的时间。在这里，x的值在将由AC君在开始前设定好但必须是正整数，游戏开始后不可以更改。

求玩家能在T秒内到达终点的情况下，AC君可以设定的x的最大值。

输入格式：

$N\ M\ T$

$S_1$

$S_2$

...

$S_N$

其中S为字符串用以表示地图，

用.表示空地

用#表示障碍物

用S表示起点

用G表示终点

输出格式：

一个整数表示答案，保证答案存在，即至少经过一个障碍物

样例：

3 4 7
S##G
.##.
..#.

3

4 4 1000000000
S###
####
####
###G

199999999

提示

对于50%的数据 $2<=T<=10^3$

对于100%的数据 $1<=N,M<=10\ ,\ 2<=T<=10^9$