Problema C - Ronda Nocturna

Clancy Wiggum é o chefe da polícia de Springfield. Como qualquer polícia que se preze, gosta muito de passar a vida comer donuts (passatempo também partilhado por Homer Simpson, diga-se). O problema é que tanto tempo passado nos vícios gastronómicos deixou-o um pouco "pesadote" e com pouca mobilidade. Ainda por cima ele é extremamente preguiçoso.

Clancy tem diariamente a tarefa de fazer uma ronda nocturna por vários locais de Springfield. Começa na esquadra, passa por todos os locais desejados pelo menos uma vez, e volta novamente à esquadra. Obviamente, quer mexer-se o menos possível nessa tarefa e por isso quer saber qual o caminho que minimiza o tempo dispendido. Será que podes ajudá-lo?

O mapa de Springfield é-te dado neste problema como uma matriz. Certas posições da matriz estão indicadas como obstáculos e não é possível passar por elas. Em cada posição, o nosso polícia pode efectuar quatro tipos de movimentos: norte, sul, este e oeste (desde que a quadrícula para onde se desloca esteja livre, claro). A mudança de uma quadricula para outra custa uma unidade.

O Problema

Dado uma mapa de Springfield com o local da esquadra de polícia e dos locais a visitar, tens de calcular o comprimento do menor caminho que começa na esquadra, passa por todos os locais a visitar pelo menos uma vez, e termina novamente na esquadra. É garantido que é sempre possível arranjar pelo menos um caminho nas condições descritas.

Input

As próximas N linhas descrevem o mapa. Cada linha é composta por M caracteres (que podem ser '#', '.', 'V' ou 'S'). '#' representa um obstáculo, '.' uma quadrícula livre, 'V' representa um local a visitar e 'S' o local da esquadra.

Existe exactamente um 'S' no input e até 10 'V''s, podendo não existir nenhum.

O mapa está sempre rodeado de '#' nos seus limites.

Output

Exemplo de Input

10 10
##########
#.V......#
#.###.##.#
#..V#..#.#
#......#.#
#..#.###V#
#....#...#
#....#S..#
#..#.#...#
##########

Exemplo de Output

36