cho.sh

Chessboard

Place as many L-trominoes as possible on a board at most 4 rows tall, where each tile's corner cell must sit on a black square and pieces block cells.

Hard8Dynamic programmingBit manipulationNo attempts yetTime limit2sMemory limit512 MB

Problem

Donghyuk has a rectangular chessboard. Its rows and columns are numbered from 0. The cell in row ii and column jj is black if i+ji+j is even and white if i+ji+j is odd. Some cells hold a piece.

Yunho has a large supply of L shaped tiles. One tile is three squares, each the same size as a board cell, joined as in the picture below.

OO
O

Yunho wants to put tiles on Donghyuk's chessboard so that all of the following hold.

  • Every tile can be rotated by 90, 180, or 270 degrees.
  • Every tile covers three cells of the board.
  • Tiles do not overlap.
  • A cell that holds a piece cannot be covered by a tile.
  • The corner cell of a tile, the cell that touches both of the other two squares, must cover a black cell of the board.

Write a program that finds the maximum number of tiles Yunho can place.

Input

The first line contains the number of rows RR and the number of columns CC of the chessboard. (1≤R≤41 \le R \le 4, 1≤C≤471 \le C \le 47)

Each of the next RR lines contains the state of one row as a string of length CC. 'X' is a cell holding a piece and '.' is an empty cell.

Output

Print the maximum number of tiles Yunho can place.