### Problem Statement

When all the presents are packed, Santa Claus has to deliver them to the children. He will start by delivering to the children in his own city. The city is a rectangular grid containing square blocks of equal size. You are given a String[] cityMap, where the j-th character of the i-th element is the block at row i, column j. There are four types of city blocks:

• 'S' - The block where Santa's home is located. This is his starting position.
• 'C' - A block where Santa must deliver presents to children. There are exactly 2 such blocks in the city.
• '#' - A closed block occupied by a factory. Santa cannot enter these blocks.
• '.' - An open block with no children.

It takes Santa one minute to move one city block north, south, east or west. He can only move in those four directions, and he cannot leave the city. When he enters a block containing children, he will deliver presents to all of them. This happens instantaneously and does not take any additional time. Since he doesn't want anybody to see him, he must change his direction after each minute and can make no stops. This means he can never make two consecutive moves in the same direction. Return the minimal number of minutes required for Santa to deliver presents to all the children in the city. If it is impossible, return -1 instead.

### Definition

 Class: TheLongWay Method: minimalTime Parameters: String[] Returns: int Method signature: int minimalTime(String[] cityMap) (be sure your method is public)

### Constraints

-cityMap will contain between 1 and 50 elements, inclusive.
-Each element of cityMap will contain between 1 and 50 characters, inclusive.
-All elements of cityMap will contain the same number of characters.
-There will be exactly 2 characters 'C' in cityMap.
-Each element of cityMap will contain only 'S', 'C', '#' and '.' characters.
-There will be exactly one character 'S' in cityMap.

### Examples

0)

 ```{"SCC", "..."}```
`Returns: 4`
 Santa cannot take a straight path because he must change his direction after every move.
1)

 `{"C.C.S"}`
`Returns: -1`
 Mission is impossible.
2)

 ```{"#.#", "CSC", "#.#"}```
`Returns: 5`
 One of the optimal ways is: west, east, north, south, east.
3)

 ```{"#.#....", "##...#.", "C#...#.", ".....#.", "..#....", "..#S.#.", ".##..#.", "###..##", "..C.#.#", "###.#.."}```
`Returns: 24`
4)

 ```{ "#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#C", ".................S..................", "C#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#" }```
`Returns: 155`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10280

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13731&pm=10280

Vasyl[alphacom]

#### Testers:

PabloGilberto , Olexiy , ivan_metelsky

#### Problem categories:

Dynamic Programming