题目描述

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

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

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

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

对于 50% 的数据，2≤T≤10^3； 对于 100% 的数据，1≤N,M≤10,  2≤T≤10^9。

输入格式

第一行三个整数 N, M, T；

接下来 N 行，每行一个长度为 M 的字符串，表示 N×M 大小的迷宫。 其中：用 . 表示空地

用 # 表示障碍物

用 S 表示起点

用 G 表示终点

输出格式

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

3 4 7

S##G

.##.

..#.

对于 50% 的数据，2≤T≤10^3；

对于 100% 的数据，1≤N,M≤10,  2≤T≤10^9。```