問題文
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