Problem Description

A square grid consists of $ H $ rows and $ W $ columns. Each cell is painted either white or black, and two white cells are designated as the start and goal points, respectively.

Takahashi wants to start from the start point and reach the goal point within $ T $ seconds. He can move from one cell to another adjacent cell (up, down, left, or right). The time it takes to move depends on the color of the destination cell: it takes $ 1 $ second if the destination is a white cell, and $ x $ seconds if it is a black cell (the color of the cell before the move does not affect the move time). Here, the value of $ x $ is chosen by you before Takahashi starts his journey. The value of $ x $ must be a positive integer and cannot be changed after Takahashi starts.

Find the maximum positive integer $ x $ such that Takahashi can reach the goal point within $ T $ seconds.

Input Format

The input is given from the standard input in the following format:

$ 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} $

• The first line contains three integers $ H, $ $ W, $ $ T $ ($ 2 $ $ ≦ $ $ H, $ $ W $ $ ≦ $ $ 10, $ $ 2 $ $ ≦ $ $ T $ $ ≦ $ $ 10^9 $). These represent the number of rows and columns of the grid, and the target time for Takahashi, respectively.
• From the second line to the $H\ +\ 1$ line, the information of each cell is given. The $i\ +\ 1$ line's $ j $ character $ s_{i,j} $ corresponds to the cell at the $ i $ row and $ j $ column. The meanings of each character are as follows:
• . : A white cell that is not designated as the start or goal point.
• S : The white cell designated as the start point.
• G : The white cell designated as the goal point.
• # : A black cell.

No other characters will appear as $ s_{i,j} $, and there will be exactly one S and one G. It is guaranteed that there exists a maximum value to find, meaning that at least one black cell must be traversed to reach the goal from the start, and it is possible to reach the goal within $ T $ seconds when $x\ =\ 1$.

Output Format

Output to the standard output the maximum positive integer $ x $ such that Takahashi can reach the goal point within $ T $ seconds.

Do not forget the newline at the end.

Sample Input and Output

Sample Input #1

2 3 10
S##
.#G

Sample Output #1

8

Sample Input #2

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

Sample Output #2

3

Sample Input #3

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

Sample Output #3

199999999

Notes/Hints

Partial Points

This problem has partial points.

• $ 40 $ points for test cases where $ 2 $ $ ≦ $ $ H, $ $ W $ $ ≦ $ $ 3, $ $ 2 $ $ ≦ $ $ T $ $ ≦ $ $ 30 $.
• Another $ 30 $ points for test cases where $ 2 $ $ ≦ $ $ T $ $ ≦ $ $ 30 $.

(※ Partial points are also set for Problem D. Please check that as well.)

Sample Explanation 1

Representing the cell at the $ i $ row and $ j $ column as $(i,\ j)$. When $x\ =\ 8$, moving $(1,\ 1)\ →\ (2,\ 1)\ →\ (2,\ 2)\ →\ (2,\ 3)$ takes $1\ +\ 8\ +\ 1\ =\ 10$ seconds to reach the goal. When $x\ \geq\ 9$, it is not possible to reach the goal within $ 10 $ seconds.

Sample Explanation 2

Moving straight right from the start point takes $2x\ +\ 1$ seconds to reach the goal. Although taking a detour can reduce the number of moves to black cells, it may take longer depending on the value of $ x $.

见题面 Input 部分

见题面 Output 部分