#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
using namespace std;

typedef istringstream ISS;
typedef ostringstream OSS;
typedef vector<string> VS;
typedef int INT;
typedef vector<INT> VI;
typedef vector<VI> VVI;
typedef pair <INT, INT> II;
typedef vector <II> VII;


typedef pair <int, II> NODE1;
typedef priority_queue <NODE1, vector<NODE1>, greater<NODE1> > QUEUE1;
typedef pair <II, II> NODE;
typedef priority_queue <NODE, vector<NODE>, greater<NODE> > QUEUE;
const int SIZE = 101;
const char STATES = 1<<6;
const char START = 'S';
const char GOAL = 'G';
const char HOGE = 'M';
const char EMPTY = '.';
const char OBJ = '#';
const int dr1[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };
const int dc1[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };
const int dr[4] = { 0, 0, 1, -1 };
const int dc[4] = { 1, -1, 0, 0 };
int W, H;
string S[SIZE];
int HR[STATES];
int HC[STATES];
int C[SIZE][SIZE];
int MC[SIZE][SIZE][STATES];
int hoges;

int sr, sc;
int gr, gc;

bool input() {
    if ( ! ( cin >> W >> H ) ) return false;
    for ( int i = 0; i < H; ++ i ) cin >> S[i];
    return true;
}

int calc_cost( int sr, int sc ) {
    QUEUE1 Q;
    Q.push( NODE1( 0, II( sr, sc ) ) );
    bool V[SIZE][SIZE];
    fill( (bool*)V, (bool*)V+SIZE*SIZE, false );
    V[sr][sc] = true;
    while ( ! Q.empty() ) {
        NODE1 node = Q.top();
        Q.pop();

        int steps = node.first;
        int r = node.second.first;
        int c = node.second.second;

        if ( S[r][c] == OBJ ) return steps > 3 ? 1 : 4 - steps;

        for ( int i = 0; i < 8; ++ i ) {
            int nr = r + dr1[i];
            int nc = c + dc1[i];
            if ( nr < 0 || nr >= H || nc < 0 || nc >= W ) continue;
            if ( V[nr][nc] ) continue;
            V[nr][nc] = true;
            int nsteps = steps + 1;
            Q.push( NODE1( nsteps, II( nr, nc ) ) );
        }
    }

    return 1;
}

int calc_cost() {
    QUEUE Q;
    Q.push( NODE( II( 0, 0 ), II( sr, sc ) ) );
    fill( (int*)MC, (int*)MC+SIZE*SIZE*STATES, INT_MAX );
    
    MC[sr][sc][0] = 0;
    int goal_state = (1<<hoges) - 1;
    while ( ! Q.empty() ) {
        NODE node = Q.top();
        Q.pop();

        int steps = node.first.first;
        int state = node.first.second;
        int r = node.second.first;
        int c = node.second.second;
        int cost = C[r][c];

        if ( r == gr && c == gc && state == goal_state ) {
            return steps;
        }

        for ( int i = 0; i < 4; ++ i ) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if ( nr < 0 || nr >= H || nc < 0 || nc >= W ) continue;
            if ( S[nr][nc] == '#' ) continue;
            int nsteps = steps + cost;
            int nstate = state;
            for ( int j = 0; j < hoges; ++ j ) {
                if ( HR[j] == nr && HC[j] == nc ) {
                    nstate |= ( 1 << j );
                    break;
                }
            }
            if ( nsteps >= MC[nr][nc][nstate] ) continue;
            MC[nr][nc][nstate] = nsteps;
            Q.push( NODE( II( nsteps, nstate ), II( nr, nc ) ) );
        }
    }

    return -1;
}

int solve() {
    hoges = 0;
    for ( int i = 0; i < H; ++ i ) {
        for ( int j = 0; j < W; ++ j ) {
            if ( S[i][j] == START ) {
                sr = i;
                sc = j;
                S[i][j] = EMPTY;
            } else if ( S[i][j] == GOAL ) {
                gr = i;
                gc = j;
                S[i][j] = EMPTY;
            } else if ( S[i][j] == HOGE ) {
                HR[hoges] = i;
                HC[hoges] = j;
                S[i][j] = EMPTY;
                hoges ++;
            }
        }
    }

      for ( int i = 0; i < H; ++ i ) {
      for ( int j = 0; j < W; ++ j ) {
          C[i][j] = calc_cost( i, j );
      }
      }

    return calc_cost();
}

int main() {
    while ( input() ) {
        cout << solve() << endl;
    }
    return 0;
}

Measured memory_bytes: 3940