問題文

正方形のマスが縦 $H$ 行、横 $W$ 列に並んでいます。各マスは白または黒で塗られており、白マスのうち $2$ つがそれぞれスタート地点とゴール地点として指定されています。

高橋君はスタート地点から出発して $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}$

• $1$ 行目には、 $3$ 個の整数 $H,$ $W,$ $T$ ($2$ $≦$ $H,$ $W$ $≦$ $10,$ $2$ $≦$ $T$ $≦$ $10^9$) が与えられる。これらはそれぞれ、マスの行数と列数、および高橋君の目標時間を表す。

• $2$ 行目から $H + 1$ 行目には、各マスの情報が与えられる。 $i + 1$ 行目の $j$ 文字目 $s_{i,j}$ が $i$ 行 $j$ 列目のマスに対応する。各文字の意味は以下の通り：

  • . : スタート地点にもゴール地点にも指定されていない白マス
  • S : スタート地点として指定された白マス
  • G : ゴール地点として指定された白マス
  • # : 黒マス

  これら以外の文字は $s_{i,j}$ として出現せず、 S および G はそれぞれちょうど $1$ 個ずつ出現する。また、入力では求める最大値が存在することが保証される。すなわち、少なくとも $1$ 度は黒マスに移動しなければスタート地点から出発してゴール地点に到着できないこと、および $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

$i$ 行 $j$ 列目のマスを $(i, j)$ で表します。 $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