using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("3 3 5");
WillReturn.Add("S.G");
WillReturn.Add("o#o");
WillReturn.Add(".#.");
//1
}
else if (InputPattern == "Input2") {
WillReturn.Add("3 3 1");
WillReturn.Add("S.G");
WillReturn.Add(".#o");
WillReturn.Add("o#.");
//-1
}
else if (InputPattern == "Input3") {
WillReturn.Add("5 10 2000000");
WillReturn.Add("S.o..ooo..");
WillReturn.Add("..o..o.o..");
WillReturn.Add("..o..ooo..");
WillReturn.Add("..o..o.o..");
WillReturn.Add("..o..ooo.G");
//18
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static int mT;
static char[,] mBanArr;
static int UB_X;
static int UB_Y;
static int mStaX;
static int mStaY;
static int mGoalX;
static int mGoalY;
// お菓子ID[お菓子の座標のHash値]なDict;
static Dictionary<int, int> mOkashiIDDict = new Dictionary<int, int>();
static int?[,] mCostMatrix;
static void Main()
{
List<string> InputList = GetInputList();
int[] wkArr = InputList[0].Split(' ').Select(pX => int.Parse(pX)).ToArray();
mT = wkArr[2];
mBanArr = CreateBanArr(InputList.Skip(1));
UB_X = mBanArr.GetUpperBound(0);
UB_Y = mBanArr.GetUpperBound(1);
int OkashiID = 4;
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
if (mBanArr[LoopX, LoopY] == 'o') {
int Hash = GetHash(LoopX, LoopY);
mOkashiIDDict[Hash] = OkashiID;
OkashiID *= 2;
}
}
}
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
if (mBanArr[LoopX, LoopY] == 'S') {
mStaX = LoopX;
mStaY = LoopY;
}
if (mBanArr[LoopX, LoopY] == 'G') {
mGoalX = LoopX;
mGoalY = LoopY;
}
}
}
// スタートもゴールもお菓子とする
mOkashiIDDict[GetHash(mStaX, mStaY)] = 1;
mOkashiIDDict[GetHash(mGoalX, mGoalY)] = 2;
mCostMatrix = new int?[mOkashiIDDict.Count, mOkashiIDDict.Count];
foreach (var EachPair in mOkashiIDDict) {
BFS(EachPair.Key);
}
int NodeCnt = mOkashiIDDict.Count;
int AllBitOn = (1 << NodeCnt) - 1;
// 最小コスト[現在位置][訪問済BitSet]なDP表
int?[,] PrevDP = new int?[NodeCnt + 1, AllBitOn + 1];
PrevDP[2, 2] = 0;
var AnswerKouho = new List<long>();
for (int I = 1; I <= NodeCnt - 1; I++) {
int?[,] CurrDP = new int?[NodeCnt + 1, AllBitOn + 1];
for (int J = 1; J <= NodeCnt; J++) {
for (int K = 0; K <= AllBitOn; K++) {
if (PrevDP[J, K].HasValue == false) continue;
for (int L = 1; L <= NodeCnt; L++) {
int CurrBit = 1 << (L - 1);
if ((K & CurrBit) > 0) continue;
int NewBitSet = K | CurrBit;
if (mCostMatrix[J - 1, L - 1].HasValue == false) continue;
int AddCost = mCostMatrix[J - 1, L - 1].Value;
int NewCost = PrevDP[J, K].Value + AddCost;
if (NewCost > mT) continue;
if (L == 1) {
AnswerKouho.Add(PopCount(K) - 1); // ゴールの分で1引く
continue;
}
if (CurrDP[L, NewBitSet].HasValue) {
if (CurrDP[L, NewBitSet] <= NewCost) {
continue;
}
}
CurrDP[L, NewBitSet] = NewCost;
}
}
}
PrevDP = CurrDP;
}
if (AnswerKouho.Count > 0) {
Console.WriteLine(AnswerKouho.Max());
}
else {
Console.WriteLine(-1);
}
}
// 始点を引数として、BFSで最短距離を求める
static void BFS(int pStaOkashiPosHash)
{
int StaOkashiID = mOkashiIDDict[pStaOkashiPosHash];
int StaX = pStaOkashiPosHash / 1000;
int StaY = pStaOkashiPosHash % 1000;
var Que = new Queue<JyoutaiDef>();
JyoutaiDef WillEnqueue;
WillEnqueue.CurrX = StaX;
WillEnqueue.CurrY = StaY;
WillEnqueue.Level = 0;
Que.Enqueue(WillEnqueue);
var VisitedSet = new HashSet<int>();
VisitedSet.Add(GetHash(StaX, StaY));
while (Que.Count > 0) {
JyoutaiDef Dequeued = Que.Dequeue();
int CurrHash = GetHash(Dequeued.CurrX, Dequeued.CurrY);
if (mOkashiIDDict.ContainsKey(CurrHash)) {
int CurrOkashiID = mOkashiIDDict[CurrHash];
int Shisuu1 = DeriveShisuu(StaOkashiID);
int Shisuu2 = DeriveShisuu(CurrOkashiID);
mCostMatrix[Shisuu1, Shisuu2] = Dequeued.Level;
mCostMatrix[Shisuu2, Shisuu1] = Dequeued.Level;
}
Action<int, int> EnqueueAct = (pNewX, pNewY) =>
{
if (pNewX < 0 || UB_X < pNewX) return;
if (pNewY < 0 || UB_Y < pNewY) return;
if (mBanArr[pNewX, pNewY] == '#') return;
if (VisitedSet.Add(GetHash(pNewX, pNewY))) {
WillEnqueue.CurrX = pNewX;
WillEnqueue.CurrY = pNewY;
WillEnqueue.Level = Dequeued.Level + 1;
Que.Enqueue(WillEnqueue);
}
};
EnqueueAct(Dequeued.CurrX, Dequeued.CurrY - 1);
EnqueueAct(Dequeued.CurrX, Dequeued.CurrY + 1);
EnqueueAct(Dequeued.CurrX - 1, Dequeued.CurrY);
EnqueueAct(Dequeued.CurrX + 1, Dequeued.CurrY);
}
}
// 2べきを引数として、2の指数を求める
static int DeriveShisuu(int pVal)
{
int WillReturn = 0;
while (pVal > 1) {
pVal /= 2;
WillReturn++;
}
return WillReturn;
}
struct JyoutaiDef
{
internal int CurrX;
internal int CurrY;
internal int Level;
}
// 座標のハッシュ値
static int GetHash(int pX, int pY)
{
return pX * 1000 + pY;
}
////////////////////////////////////////////////////////////////
// IEnumerable<string>をcharの2次元配列に設定する
////////////////////////////////////////////////////////////////
static char[,] CreateBanArr(IEnumerable<string> pStrEnum)
{
var StrList = pStrEnum.ToList();
if (StrList.Count == 0) {
return new char[0, 0];
}
int UB_X = StrList[0].Length - 1;
int UB_Y = StrList.Count - 1;
char[,] WillReturn = new char[UB_X + 1, UB_Y + 1];
for (int Y = 0; Y <= UB_Y; Y++) {
for (int X = 0; X <= UB_X; X++) {
WillReturn[X, Y] = StrList[Y][X];
}
}
return WillReturn;
}
////////////////////////////////////////////////////////////////
// C++のPopCount
////////////////////////////////////////////////////////////////
static long PopCount(long pVal)
{
long WillReturn = 0;
while (pVal > 0) {
if (pVal % 2 == 1) WillReturn++;
pVal /= 2;
}
return WillReturn;
}
}