Housewarming

Time limit1sMemory limit128 MB

Summary

Given a grid with blocked cells, find the maximum rectangle of empty cells and output twice its width plus height (the perimeter).

Level: Medium7 of 10
Topics: Dynamic programming, Stack, Array
Solved: No attempts yet

Problem

Sanggeun has bought an apartment after saving money for a long time, and he wants to invite as many friends as possible to a housewarming party.

Before the party, he wants to buy one rectangular dining table that everyone can sit around. The number of people who can sit at the table is equal to the sum of the lengths of its four sides.

The table must always be placed parallel to the sides of the apartment, and every part of the area occupied by the table must lie inside empty cells.

Given the apartment layout, find the maximum number of people Sanggeun can invite.

Input

The first line contains the apartment size R and C. (1 <= R, C <= 400)

Each of the next R lines contains a string of length C. An empty cell is written as ., and a blocked cell is written as X.

The table may be placed only on empty cells. You may assume that people are negligibly small.

Output

Print the maximum number of people Sanggeun can invite.

Examples3

Example 1
Input
```
2 2
..
..
```
Expected output
```
7
```
Example 2
Input
```
4 4
X.XX
X..X
..X.
..XX
```
Expected output
```
9
```
Example 3
Input
```
3 3
X.X
.X.
X.X
```
Expected output
```
3
```