Parking Party

Time limit2sMemory limit1024 MB

Summary

Given a grid with pillars, find the maximum number of cars that can park when each car enters along a row or column from either end.

Level: Medium7 of 10
Topics: Graph, BFS, DFS
Solved: No attempts yet

Problem

Peyman has decided to host a dinner party at his house in Zabol. His house has a rectangular parking lot that can be represented by a grid with $n$ rows and $m$ columns. A car can park in one of the $n \times m$ cells. Some cells are occupied by immovable pillars, so no car can park in or pass through them. Each row and each column has an entrance at both of its ends. When a car enters through an entrance, it moves straight forward along that row or column. It stops and parks when it reaches the opposite entrance, or when the next cell is occupied by a pillar or another parked car. A car cannot enter a row or column if its first cell is already occupied.

Peyman wants to park as many cars as possible. He can tell each arriving guest which entrance to take. Help Peyman reach this goal.

Input

The first line contains two integers $n$ and $m$ ( $1 \leq n, m \leq 1000$ ), the number of rows and columns. Each of the next $n$ lines contains a string of length $m$ made of "." and "o" characters. The $j$ -th character of the $(i+1)$ -th line is "o" if the cell in row $i$ and column $j$ has a pillar, and "." if the cell is empty.

Output

Print a single integer $k$ , the maximum number of cars Peyman can park in the lot.

Examples2

Example 1
Input
```
3 3
.o.
o.o
.o.
```
Expected output
```
4
```
Example 2
Input
```
3 4
oooo
....
...o
```
Expected output
```
7
```