问题描述

有一个由 $H$ 行 $W$ 列的正方形格子组成的图形。每个格子都被涂成白色或黑色，并且其中两个白色格子分别指定为起点和终点。

高桥君想要从起点出发，在 $T$ 秒内到达终点。高桥君可以从一个格子上下左右移动到相邻的另一个格子。在移动过程中，如果目标格子是白色格子，则需要花费 $1$ 秒钟；如果目标格子是黑色格子，则需要花费 $x$ 秒钟（移动前的格子颜色不会影响移动时间）。在高桥君出发前，你需要选择一个 $x$ 的值。$x$ 必须为正整数，并且不能在高桥君出发后更改。

请计算出高桥君在 $T$ 秒内可以到达终点的最大 $x$ 值。

输入

输入数据以以下格式从标准输入中给出：

$H$ $W$ $T$ $s_{1,1}$$s_{1,2}$ .. $s_{1,W}$ $s_{2,1}$$s_{2,2}$ .. $s_{2,W}$ : $s_{H,1}$$s_{H,2}$ .. $s_{H,W}$

• 第一行包含三个整数 $H,$ $W,$ $T$ ($2$ $≦$ $H,$ $W$ $≦$ $10,$ $2$ $≦$ $T$ $≦$ $10^9$)，分别表示格子的行数、列数以及高桥君的目标时间。

• 第二行到第 $H+1$ 行描述了每个格子的信息。第 $i+1$ 行第 $j$ 个字符 $s_{i,j}$ 表示坐标为 $(i,j)$ 的格子的状态。每个字符的含义如下：

  • . : 不是起点也不是终点的白色格子
  • S : 起点白色格子
  • G : 终点白色格子
  • # : 黑色格子

  字符串中除以上字符外不会出现其他字符。同时，S 和 G 分别出现恰好一次。输入数据保证存在最大 $x$ 值，即至少需要移动一次到黑色格子才能从起点到达终点，并且当 $x=1$ 时，在 $T$ 秒内可以到达终点。

部分点

本问题有部分得分。

• 40 分的测试用例满足 $2$ $≦$ $H,$ $W$ $≦$ $3,$ $2$ $≦$ $T$ $≦$ $30$。
• 其他 30 分的测试用例满足 $2$ $≦$ $T$ $≦$ $30$。

（※问题 D 也有部分得分，请查看那里的部分描述。）

输出

请将高桥君在 $T$ 秒内可以到达终点的最大 $x$ 值输出到标准输出中，末尾包含换行符。

示例1

2 3 10
S##
.#G

输出示例1

8

当 $x=8$ 时，可以通过 $(1,1) → (2,1) → (2,2) → (2,3)$ 的移动方式在 $1 + 8 + 1 = 10$ 秒内到达终点。当 $x \geq 9$ 时，无法在 $10$ 秒内到达终点。

示例2

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

输出示例2

3

向右直线移动，可以在 $2x + 1$ 秒内到达终点。尽管通过绕路可以减少到黑色格子的移动次数，但是取决于 $x$ 的值，可能会花费更长的时间。

示例3

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

输出示例3

199999999