QOJ.ac

QOJ

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

#6584. Wykładzina

الإحصائيات

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

为简单起见,商店里可用的地毯表示为一个高 $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