import scala.annotation.tailrec
import scala.collection.{immutable, mutable}
object Main extends App {
  import scala.io.StdIn._
  val Array(width, height) = readLine.trim.split(' ').map(_.toInt)
  val state = Array.fill(height){readLine.trim.toCharArray}
  val moveCost = Array.fill(height){Array.fill(width){1}}
  for (hole ← (0 until height).flatMap(y ⇒ (0 until width).map(Coordinate(_, y))) if state(hole) == '#') {
    for (dx ← -3 to 3; dy ← -3 to 3; pos ← Some(hole + Coordinate(dx, dy)) if state.isDefinedAt(pos)) {
      moveCost(pos) = math.max(moveCost(pos), 4 - math.max(dx.abs, dy.abs))
    }
  }
  val paper = Array.fill(height){Array.fill(width){-1}}
  val makimono = (0 until height).flatMap(y ⇒ (0 until width).collect { case x if state(y)(x) == 'M' ⇒ Coordinate(x, y) })
  for ((p, i) ← makimono.zipWithIndex) {
    paper(p) = i
  }
  val start = (0 until height).flatMap(y ⇒ (0 until width).collect { case x if state(y)(x) == 'S' ⇒ Coordinate(x, y) }).head
  val goal = (0 until height).flatMap(y ⇒ (0 until width).collect { case x if state(y)(x) == 'G' ⇒ Coordinate(x, y) }).head
  val minCost = Array.fill(height){Array.fill(width){Array.fill(1 << makimono.length){Int.MaxValue}}}
  minCost(start)(0) = 0
  val queue = mutable.PriorityQueue[((Coordinate, Int), Int)](((start, 0), 0))(Ordering.by[((Coordinate, Int), Int), Int](_._2).reverse)
  while(queue.nonEmpty) {
    val ((current, pat), cost) = queue.dequeue()
    if (minCost(current)(pat) == cost){
      for (next ← current.neighbors if paper.isDefinedAt(next) && state(next) != '#') {
        paper(next) match {
          case -1 ⇒
            if (minCost(next)(pat) > cost + moveCost(current)) {
              minCost(next)(pat) = cost + moveCost(current)
              queue.enqueue(((next, pat), cost + moveCost(current)))
            }
          case m ⇒
            if (minCost(next)(pat | (1 << m)) > cost + moveCost(current)) {
              minCost(next)(pat | (1 << m)) = cost + moveCost(current)
              queue.enqueue(((next, pat | (1 << m)), cost + moveCost(current)))
            }
        }
      }
    }
  }
  println(minCost(goal).last)
  implicit class WrapArray[T](val array: Array[Array[T]]) extends AnyVal {
    def isDefinedAt(coordinate: Coordinate): Boolean = array.indices.contains(coordinate.y) && array(coordinate.y).indices.contains(coordinate.x)
    def apply(coordinate: Coordinate): T = array(coordinate.y)(coordinate.x)
    def update(coordinate: Coordinate, value: T): Unit = array(coordinate.y)(coordinate.x) = value
  }
}

case class Coordinate(x: Int, y: Int) {
  def neighbors: Iterable[Coordinate] = List(Coordinate(x + 1, y), Coordinate(x - 1, y), Coordinate(x, y + 1), Coordinate(x, y - 1))
  def +(that: Coordinate): Coordinate = Coordinate(x + that.x, y + that.y)
}

