H. Lineism
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

On their stop in Chicago, the UTPC officers have decided to visit the Art Institute of Chicago.

One of the most famous paintings at the Art Institute of Chicago is A Sunday Afternoon on the Island of La Grande Jatte, by Georges Seurat, shown above. The painting is most well-known for its use of pointillism, whereby small dots of color blend together to enhance the painting's vibrancy. Inspired by this artwork, Edward invented his own technique known as Lineism, which uses horizontal and vertical strokes to paint lines that are 1 pixel wide and arbitrarily long.

Edward would like to paint every pixel of a shape that is convex, which means any horizontal or vertical stroke between two pixels in the shape lies entirely within the shape. The shape is also connected, which means there is a path between any two pixels in the shape using only vertical and horizontal movements within the shape. The shape is represented by an $$$n \times m$$$ grid of characters, where an 'X' denotes a pixel to paint and a '.' denotes a blank pixel that should remain unpainted.

Edward is currently busy preparing for a diamond heist, so he needs help to find the minimum number of strokes required to fill in the shape. Note that a pixel can be painted by multiple strokes.

Input

The first line of input contains $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 200$$$), the number of rows and columns in the shape, respectively.

The next $$$n$$$ lines each contain a string of length $$$m$$$, consisting of only the characters 'X' and '.', representing a row in the grid.

Output

The output should be a single integer, the minimum number of strokes required to paint every pixel of the given shape.

Example
Input
5 5
..X..
.XXX.
XXXXX
.XXX.
..X..
Output
4
Note

George can paint the 3rd row and the 2nd, 3rd, and 4th columns. It can be proven that 4 is the minimum number of strokes needed to fill in the shape.