001 - 宝探し

問題

あるところに縦にH、横にWの家がありました。海斗君は、この家で宝探しをすることにしました。この宝探しのルールは、「宝物を持った状態でゴールできれば１００点」「宝物を持っていない状態でゴールできれば７５点」「宝物を持った状態でゴールできなければ５０点」「宝物を持っていない状態でゴールもできなければ０点」となります。海斗君は、３６０度移動できる頭の良い子です。 しかし、この屋敷には障害物あり、そこを通ることはできず、そこには宝物もゴールもありません。さて、海斗君はこの家で最大何点を出すことができるのか教えてください。（もしゴールの地点に着いても、わざと入らないことも可とします）

入力

1 行目に整数 H,W が与えられる。

2 行目からH+1行目には教室の内装が与えられます

何もないところは「.」,障害物は「#」,宝物は「T」,スタート地点は「S」,ゴールは「G」とする。

出力

海斗君の獲得できる最高点数を出力してください。

制約

全ての入出力ケースについて以下を満たす。

宝物とゴールの数は必ず一つです。

• 1 ≦ H,W ≦ 500

---

入出力例

入力例1

5 5
.....
...S.
.....
....T
..G.. 

出力例1

100

入力例2

6 6
S..###
..##.#
.##..#
.#.#.#
T#.#.#
##.#.G

出力例2

50

入力例3

6 6
S..###
..##.#
.##..#
.#.#.#
G#.#.#
##.#.T

出力例2

75