Max2214 is a game that consists of a board of R rows and C columns and two kinds of blocks: Some of the blocks are 2 cells high and 2 cells wide, the others are 1 cell high and 4 cells wide. Some of the cells of the board might be marked. The objective of the game is to place the most blocks on top of the board in a way that the blocks are aligned to the rows and columns, no pair of blocks overlap, marked cells do not contain any block, and the 1×4 blocks are placed horizontally exclusively. Also, blocks must be completely inside the board.

Input

The input consists in a single test.

The test case begins with 2 integers R and C in a single line: (1 ≤ R ≤ 52) (1 ≤ C ≤ 22).

The next R lines contain C characters. Each character represents a cell. If a character is X, it means the cell is a marked cell. If the character is '.' (a dot character) it means the cell is not marked.

Output

Show a single line containing the maximum quantity of blocks that can be placed in the board following the rules mentioned above.

Example

Input:
4 5
X....
X..XX
X..XX
....X

Output:
3