Acrophobia
C: 高所恐怖症
高杉やよいは，超売れっ子アイドルである． そんな彼女には，1つ苦手なものがある． 高いところだ・・・．彼女は，極度の高所恐怖症なのである． 彼女は今回，プロデューサーの不手際により，バラエティ番組で次のようなチャレンジに挑戦することになってしまった．
今回のロケは，とある忍者屋敷のとある一室で行われる． この部屋の床には，正方形のタイルが敷き詰められており，いくつかのタイルが抜け落ちて穴になっている． この穴から落ちると数メートル下の池にまっさかさまである． やよいのチャレンジ内容は，この部屋の指定された場所からスタートし，部屋の中に置かれた全ての巻物を回収し，ゴール地点まで持っていくことである．
やよいは，部屋の中を以下のルールに従って移動できる．
- あるタイルから隣のタイルへ移動するとき，上下左右のタイルにのみ移動することができる．
- 穴に近くない場合，隣のタイルへ移動するためには，1秒だけ時間がかかる．
- 穴に近づいた場合，やよいは怖がってしまい図C-1のように移動時間がかかる．例えば，図中の矢印のように，[2][2]から[1][2]へ移動するためには，3秒かかる．
- 複数の穴が近くにある場合，最も近くにある穴に対して怖がる．
- 巻物を取るためにかかる時間は，0と仮定してよい．
|
|
|
やよいは，なるべく早くこのチャレンジを終わらせたいと考えている． あなたの仕事は，このチャレンジを終了するための最短時間を求めるプログラムを書き，やよいを助けてあげることである．
Input
忍者屋敷の床情報が与えられる．
まず，1行目に部屋の大きさを表す，WとHがスペース区切りで入力される(2 <= W, H <= 100)． 続くH行の各行には，W文字の文字列が入力される． 床情報を表す文字には，以下の種類がある．
- '.' : 歩ける床
- '#' : 穴
- 'S' : やよいが開始時に立っている場所
- 'G' : やよいが辿りつくべき場所
- 'M' : 巻物が置いてある場所
'S'と'G'と'M'は，歩ける床である． 'S'と'G'はそれぞれ，部屋の中にちょうど1個存在する．全ての巻物が揃っていない状態でゴールを通過しても構わない． 'M'は，部屋の中に最小で1個，最大で5個存在する．
Output
全ての巻物を集めて，スタートからゴールへたどり着くための最短タイムを1行に出力せよ．入力データには，必ずそのようなルートがあると仮定してよい．
行の最後には，改行を出力すること．
Sample Input 1
3 4 S.M ... ... M.G
Sample Output 1
9
Sample Input 2
4 4 S..M .... ...# #..G
Sample Output 2
18
Sample Input 3
11 7 M.........M ........... ...#.S.#... ........... ...#.G.#... ........... M.........M
Sample Output 3
62