Non-Attacking Long-Necked Deer Placement

On an N×M chessboard, some cells are forbidden for placement. You are given such a board, and your task is to place as many "long-necked deer" as possible, with the restriction that no two deer can attack each other.

The deer move like the knight in chess but without the traditional Chinese chess constraint of a blocked "horse leg." Specifically, a deer may move in any of the following eight ways:

• \( (2,1) \)
• \( (2,-1) \)
• \( (-2,1) \)
• \( (-2,-1) \)
• \( (1,2) \)
• \( (1,-2) \)
• \( (-1,2) \)
• \( (-1,-2) \)

Two deer are said to be attacking each other if one can move to the cell occupied by the other using one of these moves. Determine the maximum number of deer that can be placed on the board so that no two can attack each other.

inputFormat

The first line contains two integers N and M (1 ≤ N, M ≤ 50) representing the number of rows and columns respectively. The following N lines each contain M characters. Each character is either a '.' (denoting an available cell) or '#' (denoting a forbidden cell).

outputFormat

Output a single integer — the maximum number of non-attacking long-necked deer that can be placed on the board.

sample

3 3
...
.#.
...

5