题目描述

有一个 $H$ 行 $W$ 列的网格。自上而下第 $i$ 行，自左而右第 $j$ 列的格子记作 $(i,j)$。每个格子可能是起点、终点、空地、墙或者糖果格。$(i,j)$ 的类型由字符 $A_{i,j}$ 表示，$A_{i,j}=$ S 表示起点，$A_{i,j}=$ G 表示终点，$A_{i,j}=$ . 表示空地，$A_{i,j}=$ # 表示墙，$A_{i,j}=$ o 表示糖果格。保证起点和终点各有且仅有一个，糖果格最多有 18 个。

高桥君现在在起点。他可以多次移动到上下左右相邻且不是墙的格子。高桥君希望用不超过 $T$ 次移动到达终点。请判断是否可能做到。如果可能，请在最终停在终点的前提下，求出途中最多能访问多少个不同的糖果格。注意，同一个糖果格多次经过只计一次。

输入格式

输入通过标准输入给出，格式如下：

$H$ $W$ $T$
$A_{1,1}A_{1,2}\dots A_{1,W}$
$\vdots$
$A_{H,1}A_{H,2}\dots A_{H,W}$

输出格式

如果无法在 $T$ 步内到达终点，输出 -1。如果可以，请输出在最终停在终点的前提下，途中最多能访问的不同糖果格数量。

输入输出样例 #1

输入 #1

3 3 5
S.G
o#o
.#.

输出 #1

1

输入输出样例 #2

输入 #2

3 3 1
S.G
.#o
o#.

输出 #2

-1

输入输出样例 #3

输入 #3

5 10 2000000
S.o..ooo..
..o..o.o..
..o..ooo..
..o..o.o..
..o..ooo.G

输出 #3

18

说明/提示

限制条件

• $1 \leq H, W \leq 300$
• $1 \leq T \leq 2 \times 10^6$
• $H, W, T$ 均为整数
• $A_{i,j}$ 只可能是 S, G, ., #, o 之一
• 满足 $A_{i,j}=$ S 的 $(i,j)$ 仅有一个
• 满足 $A_{i,j}=$ G 的 $(i,j)$ 仅有一个
• 满足 $A_{i,j}=$ o 的 $(i,j)$ 最多有 18 个

样例解释 1

如 $(1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3) \rightarrow (1,3)$，移动 $4$ 次，可以访问 $1$ 个糖果格并最终到达终点。无法在 $5$ 步内访问 $2$ 个糖果格并最终到达终点，所以答案是 $1$。注意，如果 $(1,1) \rightarrow (2,1) \rightarrow (1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3)$，虽然经过 $2$ 个糖果格，但最后不在终点，因此不合法。

样例解释 2

无法在 $1$ 步内到达终点。