U562085 修理

晓莱进入到齐国芒果王国，他每天的工作是从家里出发，修理完王国之中所有坏掉的电线杆，然后回家和家人团聚。 已知齐国芒果王国是个 $n\times m$ 的区域，每块格子的类型有以下几种： ‘.’：表示该地点为空地。 ‘#’：表示该地点正在施工，晓莱无法移动到该地点。 ‘S’：表示晓莱的家。 ‘T’：表示此处有一个坏掉的电线杆。 晓莱每秒可以往上/下/左/右四个方向移动一格，且晓莱修理一个电线杆所花的时间为$t$秒，请问晓莱从家里出发修理完电线杆并最后回到家的最短时间是多少？

第一行输入三个正整数 $n,m,t$， 接下来 $n$ 行，每行包含 $m$ 个字符，表示齐国芒果王国的情况。

输出晓莱从家里出发修理完电线杆并最后回到家的最短时间，保证有解。

对于 $50 \%$ 的数据范围，保证 $ 1 \le n\leq200$，$1 \le m\leq200$，$1 \le t \le 10^{9}$ , 保证 $T$ 的数量小于等于 $3$， 并且不存在障碍。 对于 $100 \%$ 的数据范围，保证 $ 1 \le n\leq200$，$1 \le m\leq200$，$1 \le t \le 10^{9}$。 保证地图中仅有一个 $S$ ，且 $T$ 的数目大于等于 $1$ 并且小于等于 $15$ 。