Hotel

Interview

Time limit2sMemory limit1024 MB

Summary

Given a grid of blue corridor cells and red room cells, find the area of the largest red rectangle, or -1 if there is none.

Level: Easy3 of 10
Topics: Matrix, Implementation, Brute force
Solved: No attempts yet

Problem

Pavel dreamed of becoming an architect since early childhood. He often drew building plans on paper, and sometimes on tables and walls. Now he has a university degree and is a famous architect.

Once Pavel dug through his childhood drawings and found a plan of a hotel floor. The floor is a rectangle of $n \times m$ meters. Each square on the plan, representing one square meter of the floor, is painted either blue or red. Pavel realized that blue marks corridors and red marks hotel rooms.

Pavel has always followed international standards. By those standards, a hotel room must be a rectangle, so on the plan it appears as a rectangle filled with red. The sides of a room are parallel to the floor boundaries. A corridor always runs along each side of each room.

For fire safety, the floor must have corridors along its sides. So the first and last rows, and the first and last columns, of the plan are blue.

Given his plan, Pavel wants to know the maximum area of a hotel room. Write a program that finds this area.

Input

The first line contains two integers $n$ and $m$ ( $3 \le n, m \le 30$ ). The next $n$ lines each contain $m$ symbols. The symbol "*" is a blue square (one square meter of corridor), and the symbol "." is a red square (one square meter of a room).

Output

Print the area of the largest hotel room on the first line. If there are no rooms on the plan, print "-1".

Examples3

Example 1
Input
```
5 5
*****
*.***
**..*
**..*
*****
```
Expected output
```
4
```
Example 2
Input
```
4 5
*****
*.***
*.*.*
*****
```
Expected output
```
2
```
Example 3
Input
```
3 3
***
***
***
```
Expected output
```
-1
```