- Time limit: 1.00 s
- Memory limit: 512 MB
Each cell of a n \times m board either contains a turret or is empty. When a turret is activated, it instantly shoots in each of the four directions, north, east, south and west. If a turret is hit by another turret, it is activated and then destroyed. Turrets have infinitely long range.
You are given a board with some turrets in it. How many existing turrets can you destroy by placing a new turret in an empty cell and activating it?
Input
The first line of the input contains two integers, n and m, the height and width of the board. Each of the next n lines contain m characters. +
denotes that the cell is occupied by a turret and .
denotes that the cell is empty.
There is at least one empty cell.
Output
Output one integer, the maximum number of existing turrets you can destroy.
Constraints
- 1 \le n, m \le 1000
Examples
Input:
3 4 ++.. +... ..++
Output:
5
Input:
4 5 ++... ..+.. ....+ ...++
Output:
5