#arc081d. [arc081_d]Flip and Rectangles
[arc081_d]Flip and Rectangles
問題文
のマス目があります. マス目の各マスは黒か白かに塗られており,上から 番目,左から 番目のマスは, の 文字目が #
のとき黒マス,.
のとき白マスです.
すぬけ君は,マス目に対して次の操作を好きな回数行うことができます.
- マス目の任意の行または列を選び,その行または列のすべてのマスの色を反転する (すなわち,黒で塗られたマスを白に,白で塗られたマスを黒に塗り替える).
操作の後,すぬけ君はマス目に沿った長方形を 個選びます.このとき,選んだ長方形に含まれるすべてのマスは黒で塗られていなければなりません.
うまく操作を行うとき,すぬけ君が選ぶことができる最大の長方形の面積を求めてください.
制約
- は
#
,.
のみからなる.
入力
入力は以下の形式で標準入力から与えられる。
出力
すぬけ君が選ぶことができる最大の長方形の面積を出力せよ.
入力例 1
3 3
..#
##.
.#.
出力例 1
6
下図のように,上から 行目,左から 列目を反転させると, の長方形を選ぶことができます.
入力例 2
4 4
....
....
....
....
出力例 2
16
入力例 3
10 8
##...#.#
##...#.#
..###.#.
#.##.#.#
.#..#.#.
..##.#.#
##.#.#..
...#.#..
###.#.##
###..###
出力例 3
27