AT_utpc2020_h.Grid Eraser

umg 有一个 $H$ 行 $W$ 列的网格。这个网格中每个格子可以是白色或黑色。用 $S_{ij}$ 表示第 $i$ 行第 $j$ 列格子的颜色，其中 . 表示白色，# 表示黑色。umg 可以通过以下两种方式获得分数：

1. 如果第 $i$ 行的所有格子颜色相同，umg 可以删除这一行，获得 $1$ 分。删除后，如果存在的话，第 $i-1$ 行和第 $i+1$ 行会相连。
2. 如果第 $j$ 列的所有格子颜色相同，umg 可以删除这一列，获得 $1$ 分。删除后，如果存在的话，第 $j-1$ 列和第 $j+1$ 列会相连。

当网格中没有任何格子可供操作时，umg 将无法再进行任何操作。请问 umg 最多能够获得多少分？

输入通过标准输入给出，格式如下：

$H$ $W$
$S_{11} \cdots S_{1W}$
$\vdots$
$S_{H1} \cdots S_{HW}$

输出一个整数，表示 umg 可以获得的最大分数。

• $1 \leq H, W \leq 2000$
• $S_{ij}$ 仅可能为 . 或 #

举例说明

对于某个示例，umg 可以以以下步骤获得最多 $2$ 分：

1. 删除第 2 行获得 1 分，剩下的网格是：

   .##
   ##.
   

2. 删除第 2 列获得 1 分，最终网格变成：

   .#
   #.
   

此时无法再进行任何删除操作。

本翻译由 AI 自动生成