Problem Description

umg-kun has a grid with $ H $ rows and $ W $ columns. Each cell is either white or black. The color of the cell at the $ i $-th row and $ j $-th column is represented by $ S_{ij} $, where . denotes white and # denotes black. umg-kun can perform the following two types of operations in any order and any number of times to earn points:

• Choose an $ i $ such that all cells in the $ i $-th row are the same color, and delete the $ i $-th row to earn 1 point. After that, the $ i-1 $-th row and $ i+1 $-th row (if they exist) are connected.
• Choose a $ j $ such that all cells in the $ j $-th column are the same color, and delete the $ j $-th column to earn 1 point. After that, the $ j-1 $-th column and $ j+1 $-th column (if they exist) are connected.

When there are no cells left in the grid, no more operations can be performed. What is the maximum number of points umg-kun can earn?

Input Format

The input is given from the standard input in the following format:

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

Output Format

Output the answer in one line.

Sample Input and Output

Sample Input #1

3 3
.##
...
##.

Sample Output #1

2

Sample Input #2

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

Sample Output #2

24

Notes/Hints

Constraints

• $1\ \leq\ H,W\ \leq\ 2000$
• $ S_{ij} $ is either . or #

Sample Explanation 1

The optimal way to earn 2 points is as follows: Delete the 2nd row to earn 1 point. The grid then becomes:

.##
##.

Delete the 2nd column to earn another 1 point. The grid then becomes:

.#
#.

No more operations can be performed.

见题面 Input 部分

见题面 Output 部分