#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

struct Hole{
	int row,col;
};

struct Info{
	Info(int arg_row,int arg_col,int arg_state,int arg_total_cost){
		row = arg_row;
		col = arg_col;
		state = arg_state;
		total_cost = arg_total_cost;
	}

	int row,col,state,total_cost;
};

int H,W;
int diff_row[4] = {-1,0,0,1},diff_col[4] = {0,-1,1,0};

bool rangeCheck(int row,int col){
	if(row >= 0 && row <= H-1 && col >= 0 && col <= W-1)return true;
	else{
		return false;
	}
}

int main(){

	int POW[6];

	for(int i = 0; i < 6; i++)POW[i] = pow(2,i);

	scanf("%d %d",&W,&H);

	char map[H][W+1];

	int hole_num = 0;
	Hole hole[10000];

	int makimono_num = 0;

	int start_row,start_col,goal_row,goal_col;

	for(int i = 0; i < H; i++){
		scanf("%s",map[i]);
		for(int k = 0; k < W; k++){
			switch(map[i][k]){
			case 'S':
				start_row = i;
				start_col = k;
				map[i][k] = '.';
				break;
			case 'G':
				goal_row = i;
				goal_col = k;
				map[i][k] = '.';
				break;
			case 'M':
				map[i][k] = '0' + makimono_num;
				makimono_num++;
				break;
			case '#':
				hole[hole_num].row = i;
				hole[hole_num].col = k;
				hole_num++;
				break;
			}
		}
	}

	int move_cost[H][W];

	for(int i = 0; i < H; i++){
		for(int k = 0; k < W; k++)move_cost[i][k] = 1;
	}

	for(int i = 0; i < hole_num; i++){
		for(int row = 0; row < H; row++){
			for(int col = 0; col < W; col++){
				if(map[row][col] == '#')continue;
				move_cost[row][col] = max(move_cost[row][col],4-max(abs(hole[i].row-row),abs(hole[i].col-col)));
			}
		}
	}

	int limit = POW[makimono_num];

	int dp[H][W][limit];

	for(int row = 0; row < H; row++){
		for(int col = 0; col < W; col++){
			for(int state = 0; state < limit; state++)dp[row][col][state] = BIG_NUM;
		}
	}

	queue<Info> Q;

	Q.push(Info(start_row,start_col,0,0));

	int next_row,next_col,next_state;

	while(!Q.empty()){

		if(Q.front().state == limit-1 && Q.front().row == goal_row && Q.front().col == goal_col){
			Q.pop();
		}else if(Q.front().total_cost > dp[Q.front().row][Q.front().col][Q.front().state]){
			Q.pop();
		}else{
			for(int i = 0; i < 4; i++){
				next_row = Q.front().row + diff_row[i];
				next_col = Q.front().col + diff_col[i];

				if(rangeCheck(next_row,next_col) == false || map[next_row][next_col] == '#')continue;

				next_state = Q.front().state;
				if(map[next_row][next_col] >= '0' && map[next_row][next_col] <= '4'){
					if(!(Q.front().state & (1 << (map[next_row][next_col]-'0')))){
						next_state += POW[map[next_row][next_col]-'0'];
					}
				}

				if(dp[next_row][next_col][next_state] > Q.front().total_cost+move_cost[Q.front().row][Q.front().col]){
					dp[next_row][next_col][next_state] = Q.front().total_cost+move_cost[Q.front().row][Q.front().col];
					Q.push(Info(next_row,next_col,next_state,dp[next_row][next_col][next_state]));
				}
			}
			Q.pop();
		}
	}

	printf("%d\n",dp[goal_row][goal_col][limit-1]);

	return 0;

}

Measured memory_bytes: 4776