問題文

うしくん と イノシシ が迷路に閉じ込められてしまいました。

迷路は H 行 W 列のマス目で表されています。上から i 行目、左から j 列目にあるマスを (i,j) で表し、マス (i,j) の情報は s_{ij} で与えられます。

• s_{ij} が S のとき、マス (i,j) はスタート地点で、うしくん は最初このマスにいます。
• s_{ij} が G のとき、マス (i,j) はゴール地点です。
• s_{ij} が # のとき、マス (i,j) は壁のマスで、このマスを通ることはできません。
• s_{ij} が @ のとき、マス (i,j) にはイノシシがいます。
• s_{ij} が . のとき、マス (i,j) は空のマスです。

うしくん は壁のマス以外の上下左右に隣接するマスに移動することができます。

' 安全なマス ' を、そこから X 回以下の移動で行くことのできる全てのマスにイノシシがいないようなマスと定義します。

うしくん がスタート地点から安全なマスのみを通ってゴール地点に到達するまでの最小の移動回数を求めてください。

制約

• 4 \leq H, W \leq 10^3
• 0 \leq X \leq 10^6
• s_{ij} は S または G または # または . または @ からなる
• スタート地点とゴール地点はそれぞれ 1 つずつ存在する
• イノシシがいるマスは 1 つ以上存在する
• スタート地点は安全なマスであることが保証されている
• 迷路の外側 1 マスは壁で囲われている
• H,W,X は整数

部分点

• H, W \leq 50 を満たすデータセットに正解した場合、30 点が与えられる。

入力例 1

6 5 1
#####
#S.@#
#...#
#...#
#@.G#
#####

出力例 1

5

(2,2) → (3,2) → (3,3) → (4,3) → (4,4) → (5,4) と移動することで、スタートから安全なマスのみを通ってゴールまで 5 回で移動できます。

入力例 2

5 6 0
######
#S...#
#@@@.#
#G...#
######

出力例 2

8

入力例 3

5 5 1
#####
#S..#
#...#
#.@G#
#####

出力例 3

-1

ゴールが安全なマスとは限りません。