012 - Alice's Magic

時間制限 1 秒 / メモリ制限 64 MB / 得点 100 / x 16 /


TLE
1sec
MLE
64MB
得点
100

問題

幻想郷の一角。魔法の森。

そこには頭を悩ませる一人の魔法使いが居た。

彼女の名前はアリス。人形を操る魔法使いだ。

彼女は今、家のとある部屋の中にできるだけ大きな魔法陣を作ろうとしている。

魔法陣は縦と横 N * N マスの正方形である。

しかしその部屋には多くの人形がスタックされており、考えるのに苦悩している。

魔法陣は、人形のない床にのみ作ることができる。

人形は移動させることが出来る。

さて、彼女の部屋の俯瞰図が与えられるので、

作れる魔法陣の最大の面積を出力せよ。

入力

一行目に、部屋の縦の広さと横の広さ h , w が与えられる。

次の行から、h行に渡り、部屋の状態が与えられる。

# のとき人形、. の時何もないことを示す。

h w
m1,1 m1,2 ... m1,w
m2,1 m2,2 ... m2,w
..
..
mh,1 mh,2 ... mh,w

出力

作成できる魔法陣の最大の面積を出力せよ。

制約

  • 1 ≦ H,W ≦ 2000

入出力例

入力例壱

3 4
##.#
#.#.
#...

出力例壱

4

(2,3)の人形を(1,3)に移動させることで、

一辺が2、面積4の魔法陣を作ることが出来る。

入力例弐

4 6
.##.#.
##..##
...#..
.#..##

出力例弐

9