Description

Jack is planning to renovate his house to make his room as large as possible. However, since Jack doesn't have much money, he wants to create a spacious room with minimal effort.

Jack's house is represented as a grid with height $H$ and width $W$. Each cell in the grid is in one of the following states:

• . : A floor that Jack can freely move through.
• # : A wall that Jack cannot pass through.
• S : The cell where Jack is currently located, which is also a floor.

Jack can move to adjacent floor cells in the grid, either up, down, left, or right. He cannot move outside the boundaries of his house.

In this renovation, Jack can destroy up to one wall and turn it into a floor. Determine the maximum number of cells Jack can reach from the currently located position after making this change.

Input Format

The input consists of a single test case of the following format.

$$\begin{aligned} & H \ W \\ & l_{1} \\ & l_{2} \\ & \vdots \\ & l_{H} \end{aligned}$$

The first line contains two integers, $H$ and $W$, representing the height and width of the grid, respectively. Both $H$ and $W$ are between $2$ and $500$ (both inclusive).

The next $H$ lines each contain a string of length $W$, representing the grid. Each string $l_{i}$ consists of the characters . (floor), # (wall), and S (Jack's starting position). It is guaranteed that the grid contains exactly one S.

Output Format

Output a single integer, the maximum number of cells Jack can reach from his starting position after optionally destroying one wall.

3 5
.#...
.####
#.#.S

6

3 7
.......
...S...
.......

21