#include <bits/stdc++.h>

using namespace std;

namespace {
    const int INF = 1<<28;

    int W, H;
    vector<string> F;
    void input() {
        cin >> W >> H;
        F.clear(); F.resize(H);
        for (int i = 0; i < H; i++) {
            cin >> F[i];
        }
    }

    void find_pos(int& sy, int &sx, char c) {
        sy = -1, sx = -1;
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                if (F[i][j] == c) {
                    sy = i;
                    sx = j;
                    return;
                }
            }
        }
        assert(false);
    }

    struct P {
        int y, x, d;
        P(int y, int x, int d) : y(y), x(x), d(d) {}
    };

    struct S {
        int bit, y, x, d;
        S(int bit, int y, int x, int d) : bit(bit), y(y), x(x), d(d) {}
        bool operator<(const S& p) const {
            return d > p.d;
        }
    };
    ostream& operator<<(ostream& os, const S& s) {
        return os << "S(" << s.bit << " (" << s.y << "," << s.x << ")" << " " << s.d << ")";
    }

    int construct_map(map< pair<int, int>, int >& M) {
        int c = 0;
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                if (F[i][j] == 'M') {
                    M[make_pair(i, j)] = c++;
                }
            }
        }
        return c;
    }

    const int dy[] = {-1, 0, 1, 0};
    const int dx[] = {0, 1, 0, -1};

    const int DY[] = {-1, -1, 0, 1, 1, 1, 0, -1};
    const int DX[] = {0, 1, 1, 1, 0, -1, -1, -1};

    vector< vector<int> > D;
    void solve() {
        D.clear(); D.resize(H, vector<int>(W, 1));
        queue<P> Q;
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                if (F[i][j] == '#') {
                    D[i][j] = INF;
                    Q.push(P(i, j, 4));
                }
            }
        }
        while (!Q.empty()) {
            P c = Q.front(); Q.pop();
            for (int i = 0; i < 8; i++) {
                int ny = c.y + DY[i],
                    nx = c.x + DX[i];
                int nd = c.d - 1;
                if (ny < 0 || ny >= H) continue;
                if (nx < 0 || nx >= W) continue;
                if (D[ny][nx] < nd) {
                    D[ny][nx] = nd;
                    Q.push(P(ny, nx, nd));
                }
            }
        }

        int sy, sx;
        find_pos(sy, sx, 'S');

        map< pair<int, int>, int > M;
        int N = construct_map(M);

        priority_queue<S> PQ;
        static int X[1<<5][101][101];
        for (int i = 0; i < 32; i++) for (int j = 0; j < 100; j++) for (int k = 0; k < 100; k++) {
            X[i][j][k] = INF;
        }
        X[0][sy][sx] = 0;
        PQ.push(S(0, sy, sx, 0));
        while (!PQ.empty()) {
            S c = PQ.top(); PQ.pop();
            for (int i = 0; i < 4; i++) {
                int ny = c.y + dy[i],
                    nx = c.x + dx[i];
                if (ny < 0 || ny >= H) continue;
                if (nx < 0 || nx >= W) continue;
                int nbit = c.bit;
                if (F[ny][nx] == 'M') {
                    nbit |= (1 << M[make_pair(ny, nx)]);
                }
                int nd = D[c.y][c.x] + c.d;
                if (X[nbit][ny][nx] > nd) {
                    X[nbit][ny][nx] = nd;
                    PQ.push(S(nbit, ny, nx, nd));
                }
            }
        }

        int gy, gx;
        find_pos(gy, gx, 'G');
        cout << X[(1 << N) - 1][gy][gx] << endl;
    }
}

int main() {
    input(); solve();
    return 0;
}

Measured memory_bytes: 2728