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 1x4 blocks are placed horizontally exclusively. Also, blocks must be completely inside the board.

Input

The input consists in a single test case with a 15 seconds execution limit.

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