001 - 宝探し

時間制限 0.5 秒 / メモリ制限 64 MB / 得点 100 / x 4 /


TLE
0.5sec
MLE
64MB
得点
100

問題

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

入力

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