AT_utpc2020_h Grid Eraser

[problemUrl]: https://atcoder.jp/contests/utpc2020/tasks/utpc2020_h 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 くんは最大で何ポイントを得ることができるでしょうか？

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ S_{11} $$ \cdots $$ S_{1W} $ $ \vdots $ $ S_{H1} $$ \cdots $$ S_{HW} $

答えを $ 1 $ 行に出力せよ。

### 制約 - $ 1\ \leq\ H,W\ \leq\ 2000 $ - $ S_{ij} $ は `.` または `#` ### Sample Explanation 1 次のように操作を行い $ 2 $ ポイントを得るのが最適となります。 $ 2 $ 行目を削除して $ 1 $ ポイントを得る。その後、グリッドは以下のようになる。 ``` .## ##. ``` $ 2 $ 列目を削除して $ 1 $ ポイントを得る。その後、グリッドは以下のようになる。 ``` .# #. ``` もう操作を行うことはできない。