H - Grid Eraser Editorial /

Time Limit: 1 sec / Memory Limit: 1024 MB

問題文

umg くんは縦 H 行、横 W 列のグリッドを持っています。各マスは白色または黒色です。上から i 行目、左から j 列目のマスの色は S_{ij} で表され、 . のとき白、 # のとき黒です。 umg くんは、以下の 2 種類の操作を好きな順序で好きな回数行うことでポイントを得ます。

  • i 行目のマスがすべて同じ色であるような i を選び、 i 行目を削除して 1 ポイントを得る。その後、 i-1 行目と i+1 行目は(存在すれば)連結される。
  • j 列目のマスがすべて同じ色であるような j を選び、j 列目を削除して 1 ポイントを得る。その後、 j-1 列目と j+1 列目は(存在すれば)連結される。

グリッドのマスが 1 つも存在しない場合、操作を行うことができません。 umg くんは最大で何ポイントを得ることができるでしょうか？

制約

  • 1 \leq H,W \leq 2000
  • S_{ij} は . または #

入力

入力は以下の形式で標準入力から与えられる。

H W  
S_{11}\cdotsS_{1W}  
\vdots  
S_{H1}\cdotsS_{HW}

出力

答えを 1 行に出力せよ。

入力例1

3 3
.##
...
##.

出力例1

2

次のように操作を行い 2 ポイントを得るのが最適となります。

2 行目を削除して 1 ポイントを得る。その後、グリッドは以下のようになる。

.##
##.

2 列目を削除して 1 ポイントを得る。その後、グリッドは以下のようになる。

.#
#.

もう操作を行うことはできない。

入力例2

7 56
........................................................
.#...#..#####..#####...####..#####..#####..#####..#####.
.#...#....#....#...#..#..........#..#...#......#..#...#.
.#...#....#....####...#......#####..#...#..#####..#...#.
.#...#....#....#......#......#......#...#..#......#...#.
..###.....#....#.......####..#####..#####..#####..#####.
........................................................

出力例2

24