Vampire's Treasure X89012

There are many big treasures hidden in the caves! However, it is guarded by a vampire. You want to collect as many of these treasures as possible, while avoiding being catched by the vampire. Luckily, the vampire is quite stupid.

The rules are as follows:

• The cave is composed of squares. Some of them are empty (.), and some contain walls (#), treasure (T), you (S), or the vampire (V).
• You can move to an adjacent square in 8 directions (including diagonals). You cannot wait.
• After your each move, the vampire can move too.
• The vampire is able to detect you telepathically, so it will always try to move to the place which is the closest to you (in Euclidean distance). If there are two best directions, it will become confused, and wait.
• You die when you run into the vampire, or the vampire runs into you.
• Both you and vampire can move into treasures, but not into walls or outside the cave. You collect treasures immediately, as long as the vampire does not catch you in the same turn.

Input The first line of input contains two numbers X and Y, which are the dimensions of the board (1 ≤ X ≤ 20, 1 ≤ Y ≤ 15).

The following Y lines contains X characters each. This is the cave map, made of .#TSV characters. There is at most one S, at most one V, and at most six T.

Output

Output two numbers: the amount of treasure that you are able to collect, and the minimum number of turns required. For now, you do not care about how you will escape the cave...

The solution is as follows (Y-you, V-vampire, y,v-previous positions):

After 8 steps:

....................
.y.....Y..V.........
..y.yyy###.vvv......
...y###y.#.###v###..
....#....#.....v....
....#....#......v...
.................vT.
##...............Tv.
T#..................

After 12 steps:

....................
.y.....vvvv.........
..y.yyV###.vvv......
...y###y.#.###v###..
....#..y.#.....v....
....#...Y#......v...
.................vT.
##...............Tv.
T#..................

After 23 steps:

....................
.y.....vvvv.........
..y.yyv###.vvv......
...y###v.#.###v###..
....#..yv#.....v....
....#...v#......v...
.........v.....vVYy.
##........v...v..yv.
T#.........vvvyyy...