Migrated from Lutece 3140 殊途同归Ⅱ

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

在某个雨夜，Tri17 做了一个很漫长的梦。在梦里，他再次见到了心爱的她，共同漫步于学校内。 学校的地图可以简化为一个矩形，含有 $n*m$ 个位置。其中S代表相遇的起点，G代表要走到的终点，o代表约会地点，.代表可以走的路，#代表无法通行的位置。 Tri17 将从起点出发，每次使用 $1$ 个单位时间，向相邻的可通行位置移动（即向上，向下，向左，向右）。多次经过同一个约会地点视作仅经过一次。 由于梦的时间是有限的，现在他想知道，在至多 $T$ 个单位时间内从起点到终点的基础上，最多能经过多少个约会地点。

Input

输入的第一行包括三个正整数 $n,m,T$ ，分别表示地图的大小和限制的时间。 接下来 $n$ 行 $m$ 列输入地图。

Output

输出一个整数，表示答案。如果在限制时间里无法到达终点则输出 $-1$。

Samples

3 3 8
S.G
o#.
.#o

2

3 3 4
S.G
.#o
o#.

1

1 3 1
S.G

-1

Constraints

$1 \le n,m \le 300,1\le T \le 10^9$ 保证约会地点的数量不超过 $18$ 个，且起点，终点，约会地点所在的位置不会重复。

Note

对于样例1，存在最优走法：↓↑→→↓↓↑↑，使两个约会点都被经过。 对于样例2，存在最优走法：→→↓↑。 对于样例3，无法在限制时间内走到终点。

题目背景：别去组团门口啦！清水河约会怎么走？

Resources

2024 UESTC ICPC Training for Search and Dynamic Programming