Problem Description

There is a board divided into $ H $ rows and $ W $ columns, and each cell on the board is either "has a coin facing up", "has a coin facing down", or "has no coin".

Additionally, there are $ W + H $ cards, each labeled with "Row 1", "Row 2", ..., "Row H", "Column 1", "Column 2", ..., "Column W".

Using this board and these cards, two players will play a game.

The game is played by alternating turns until it ends. Each turn consists of the following steps:

1. The player on turn freely chooses one card and removes it.
2. All coins in the row or column written on the removed card are flipped.
3. If there are no more cards to remove, or if all coins on the board are facing up, the game ends.

After the game ends, each player earns points based on the state of the game:

• The player who removed the last card earns 1 point.
• If all coins on the board are facing up, both players earn an additional 2 points.

Determine the total points the first player will earn when both players act optimally to maximize their total points.

Input Format

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

$ m_{ij} $ represents the state of the cell at row $ i $ and column $ j $, where . means no coin, o means a coin facing up, and x means a coin facing down.

$ H $ $ W $ $ m_{11} $ $ m_{12} $ $ ... $ $ m_{1W} $ $ m_{21} $ $ m_{22} $ $ ... $ $ m_{2W} $ $ : $ $ m_{H1} $ $ m_{H2} $ $ ... $ $ m_{HW} $

Output Format

Output the total points the first player will earn when both players act optimally to maximize their total points in one line.

Sample Input and Output

Sample Input #1

2 5
.x.x.
x.o.x

Sample Output #1

3

Sample Input #2

7 2
x.
xx
x.
xx
x.
xx
x.

Sample Output #2

3

Sample Input #3

4 3
x.o
.x.
x.x
...

Sample Output #3

1

Sample Input #4

5 1
x
o
.
o
x

Sample Output #4

2

Sample Input #5

39 40
.........o..............................
.............................o..........
.................o......................
......o...............................x.
...x......o.............................
...........................o......o.....
.........................x..............
.................o.............o........
..................x.....................
.............o..........................
.......................................o
...............o........................
.....x.....o............................
..................o.....................
..o.........o...........................
...............x........................
.......o............................x...
........................x.....o.........
...................o.........o..........
........x..........................o....
......................o...o.............
..............o..................o......
..............x.........................
x.......................................
..o....................x................
.........................o..............
.o...................................o..
.................................o......
.o..................x...................
...........o....o.......................
.............x..........................
...............................x........
....o..............................o....
..........................o.x...........
...................x....................
.....................................o..
.........x..............................
o......................................o
.....................x..........o.......

Sample Output #5

3

Sample Input #6

38 39
.......o............................x..
.........x.............................
................x......................
............x..........................
.................x..........o..........
..................................o..o.
...............................o.......
.....................x..........o......
.............o.........................
..o....................o...............
....x..................................
...................o...................
..................o....................
.....x.....o...........................
.o..................o..................
....................o......x...........
.........................o.............
..................x....................
...............o.......................
......o...............................x
.......................o.........x.....
...............x.......................
.o.....................................
.........o.............................
o......................................
..............o.......o................
............o......o...................
........o..........................o...
..........................o.o..........
...x......o............................
......................x................
.............x.........................
o...o..................................
........o....................x.........
..............o........................
................o..............o.......
........................x.....o........
.........................x.............

Sample Output #6

2

Notes/Hints

Constraints

• $1 \leq W, H \leq 2,000$
• $ m_{ij} $ is one of ., o, or x.
• At least one coin is facing down.

Partial Points

If you solve the dataset satisfying the following additional constraints, you will be awarded 30 points:

• Each row has at least one coin facing down.
• Each column has at least one coin facing up or down.

If you solve the dataset without the additional constraints, you will be awarded an additional 370 points.

Sample Explanation 1

This input example satisfies the additional constraints.

Sample Explanation 2

This input example satisfies the additional constraints.

见题面 Input 部分

见题面 Output 部分