Problem BT
Treasure Hunt

Image by Steven Johnson

You are a treasure hunter searching for gold in the wild. Luckily you got a map of the area from a black marketeer. The map clearly shows where a box of gold is along with the surrounding terrain. Of course, you want to head to the treasure as fast as possible. However, the trip might not be easy.

The area is described by a grid of $N$ rows and $M$ columns. You are currently located at the cell labeled ‘S’. The treasure is located at the cell labeled ‘G’. Despite your eagerness for the treasure, you cannot keep moving tirelessly. The surrounding area has different landforms: plain (‘.’), forest (‘F’), mountain (‘M’) or river (‘#’). Rivers are impassable since no boats are currently available. You can navigate in four directions (up, down, left, right) between neighboring cells.

At the beginning of your trip you have $K$ stamina points. Moving onto a plain, forest, and mountain costs you $1$, $2$, and $3$ points of stamina respectively. Once you run out of stamina and can no longer move to nearby cells, you must camp and rest. Your stamina is replenished to the full $K$ points on the second day so that you can start moving again.

Plan wisely with the map and determine the minimum number of days you need to reach the treasure.

Input

The first line has three integers $N$, $M$ ($1\le N,M\le 50$), and $K$ ($1\le K\le 100$). Each of the next $N$ lines has $M$ characters describing the grid shown by the treasure map. The grid contains only characters ‘.’, ‘F’, ‘M’, ‘#’, ‘S’, and ‘G’. It is guaranteed that ‘S’ and ‘G’ appear exactly once in the grid. You may assume your starting point (‘S’) and the treasure (‘G’) are both on a plain.

Output

Output the minimum number of days you need to reach the treasure. If it is impossible to get to the treasure, output “-1”.

2 5 4
S#.F.
.MFMG

3

1 2 1
GS

1

2 2 10
S#
#G

-1

1 7 4
SMMMMMG

5