Spare the Ewoks!

Interview

Time limit3sMemory limit128 MB

Summary

Given an m by n grid with blocked cells, choose up to three non-overlapping axis-aligned rectangles to maximize the total covered area.

Level: Hard8 of 10
Topics: Dynamic programming, Prefix sum, Brute force
Solved: No attempts yet

Problem

The Galactic Empire wants to build a new base on the forest moon of Endor. Endor is home to a species of small, cuddly creatures called the Ewoks, and you have been ordered not to disturb any existing Ewok home. Subject to that, you must make the base as large as possible in total area, and that area may be split among up to three rectangular buildings.

You are given a map of Endor as an $m \times n$ grid. Each cell is either empty or an Ewok home. Place up to three (possibly fewer) axis-aligned rectangular buildings on the grid so that no two buildings overlap and no building is placed on an Ewok home. Maximize the total area covered by the buildings.

Input

The input contains several test cases.

Each test case begins with a line containing two integers $m$ and $n$ ( $1 \le m \le 250$ , $1 \le n \le 250$ ), the number of rows and columns of the grid. The next $m$ lines describe the map; each line contains exactly $n$ characters, where . (a period) is an empty cell and e (a lowercase letter e) is an Ewok home.

The input ends with a line containing 0 0, which must not be processed.

Output

For each test case, print a single line containing one integer: the maximum total area that can be covered by up to three non-overlapping rectangular buildings that avoid every Ewok home.

Examples6

Example 1

Input

1 2
..
5 6
eee...
ee...e
ee...e
e...ee
e..eee
8 12
eee...eee...
eee...eee...
ee...eee..ee
eee...eee...
ee...eee...e
eee..eee..ee
ee..eee..eee
eee..eee...e
0 0

Expected output

2
13
22

Example 2
Input
```
1 1
.
0 0
```
Expected output
```
1
```
Example 3
Input
```
1 1
e
0 0
```
Expected output
```
0
```
Example 4
Input
```
4 5
.....
.....
.....
.....
```
Expected output
```
20
```
Example 5
Input
```
1 8
.e..e...
0 0
```
Expected output
```
6
```

Example 6

Input

7 7
......e
......e
..e....
....e..
e...e..
...e...
....e..

Expected output