题目描述

我们有一个 $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$ 次移动内到达目标位置。判断是否可能。如果可能，则找出他能够在到达目标位置时访问的糖果位置的最大数量，其中他必须结束。即使多次访问同一个糖果位置，也只计数一次。

约束条件

• $1 \leq H,W \leq 300$
• $1 \leq T \leq 2 \times 10^6$
• $H$、$W$ 和 $T$ 是整数。
• $A_{i,j}$ 是 S、G、.、# 和 o 中的一个字符。
• 恰有一对 $(i,j)$ 满足 $A_{i,j}=$ S。
• 恰有一对 $(i,j)$ 满足 $A_{i,j}=$ G。
• 最多有 $18$ 对 $(i,j)$ 满足 $A_{i,j}=$ o。

输入

从标准输入读入输入数据，输入格式如下：

$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

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

示例输出1

1

如果他通过 $(1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3) \rightarrow (1,3)$ 进行四次移动，他可以访问一个糖果位置并在目标位置结束。他不能通过五次或更少的移动访问两个糖果位置并在目标位置结束，所以答案是 $1$。

注意，通过 $(1,1) \rightarrow (2,1) \rightarrow (1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3)$ 进行五次移动来访问两个糖果位置是无效的，因为他无法在目标位置结束。

示例输入2

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

示例输出2

-1

他无法在一次或更少的移动内到达目标位置。

示例输入3

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

示例输出3

18