题目背景

给一张图，图中有起点 $S$ ，终点 $G$ ，糖果 $o$（不超过 $18$ 个）。给定时间 $T$ ，最多能捡多少个糖果？

题目描述

有一个行数为 $n$ 列数为 $m$ 的网格图。网格中的每个方格都是以下几种方格之一：起点方格S、终点方格G、空方格.、墙壁方格#和糖果方格o。

保证恰好一个起点和一个终点。最多有 $18$ 个糖果方格。

奆现在位于起点方格。他可以重复移动到垂直或水平相邻的非墙方格。他希望最多用 $T$ 步到达终点位置。判断这是否可能。如果可能，找出他在到达目标方格的途中最多能捡到的糖果数量。

输入格式

输入第一行输入三个整数 $n,m,T$。

接下来输入一个 $n$ 行 $m$ 列的字符矩阵。

输出格式

如果 $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

说明/提示

对于$30\%$ 的数据：$min(n,m)=1$

对于另外 $30\%$ 的数据：$1\le n,m\le 10$

对于 $100\%$ 的数据：$1\le n,m\le 300,1\le T\le 2\times 10^6$

最多有 $18$ 个糖果方格。