QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 128 MB Total points: 100

# 6584. Wykładzina

Statistics

Bajtazar ogląda właśnie w sklepie wykładzinę. Niestety na niektórych fragmentach wykładziny są brzydko wyglądające wady fabryczne. Ponieważ Bajtazar chciałby zakupić jak najwięcej wykładziny, postanowił, że dopuszcza kupienie wykładziny z jedną wadą. Postawi w tym miejscu dużą donicę z kwiatami i nie będzie problemu.

Dla uproszczenia wykładzinę dostępną w sklepie reprezentujemy jako prostokąt o wysokości $w$ i szerokości $s$ podzielony na $w \times s$ kwadracików o rozmiarach $1 \times 1$. Dla każdego kwadracika wiemy, czy zawiera on wadliwy fragment wykładziny. Bajtazar chciałby kupić jak największy prostokątny kawałek wykładziny składający się z kwadracików jednostkowych, w którym co najwyżej jeden kwadracik jest wadliwy. Ile wynosi pole powierzchni takiego kawałka?

Input Format

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite $w$ i $s$ ($1 \le w, s \le 2\,000$), oznaczające odpowiednio wysokość i szerokość wykładziny dostępnej w sklepie. Kolejne $w$ wierszy opisuje wykładzinę. Każdy z tych wierszy zawiera napis składający się z $s$ znaków . (kwadracik bez wad) i # (kwadracik wadliwy), który opisuje poszczególne kwadraciki jednostkowe wykładziny.

Output Format

Wypisz maksymalne pole powierzchni prostokątnego kawałka wykładziny, który składa się z kwadracików jednostkowych i zawiera co najwyżej jeden wadliwy kwadracik.

Examples

Input

4 5
#.#..
....#
..#..
....#

Output

12

巴伊塔扎尔正在商店里看地毯。不幸的是,地毯的某些部分有难看的工厂缺陷。因为巴伊塔扎尔想买尽可能多的地毯,他决定允许购买带有一个缺陷的地毯。他会在那个地方放一盆大花,就没有问题了。

为简单起见,商店里可用的地毯表示为一个高 $w$ 宽 $s$ 的矩形,分成 $w$ × $s$ 个 1 × 1 的小方块。对于每个小方块,我们知道它是否包含地毯的缺陷部分。巴伊塔扎尔想买一个最大的矩形地毯块,由单位小方块组成,其中最多只有一个小方块有缺陷。这样一块地毯的面积是多少?

Input Format

输入的第一行包含两个整数 $w$ 和 $s$ ($1 \le w, s \le 2\,000$),分别表示商店中可用地毯的高度和宽度。接下来的 $w$ 行描述地毯。每行包含一个由 $s$ 个字符组成的字符串,字符为 . (无缺陷的小方块) 和 # (有缺陷的小方块),描述地毯的各个单位小方块。

Output Format

输出由单位小方块组成且最多包含一个缺陷小方块的矩形地毯块的最大面积。

Examples

Input

4 5
#.#..
....#
..#..
....#

Output

12