Robot

Romas does not like cleaning, so he bought an autonomous robotic vacuum cleaner. The robot is quite primitive, though. While cleaning, it moves straight forward until it hits an obstacle (such as a piece of furniture or a wall). Then it turns right by 90 degrees and repeats the same motion.

Romas's flat plan can be modelled as an $N \times M$ grid. Each cell is either a free area that the robot can clean or an occupied cell that contains an obstacle. The robot moves parallel to the sides of the grid.

Romas switches the robot on before he leaves for work. He wants the largest possible area to be cleaned when he arrives.

The robot can be started from any free cell in any direction: up, down, left, or right. Find the largest area the robot can clean.

The first line contains two integers $N$ and $M$, the dimensions of the flat. The next $N$ lines describe the flat plan. Each line contains $M$ characters. . marks a free cell and # marks an occupied cell. All border cells are occupied, and there is at least one free cell.

Print a single integer: the largest number of cells the robot can clean.

$3 \le N, M \le 1000$