Background

A small card game called “Land-Occupying Fighter” has deeply attracted Little A. She is currently practicing card placement, but she is not skilled yet, so she wants to ask you, who are good at programming, to solve this problem.

Problem Description

The detailed rules of the game are as follows: the game is played on an $n \times m$ grid. . means this cell can be used for placement, and # means this cell cannot be used for placement. You have $4$ different shapes of cards, and there is only one card of each shape. You need to place the cards onto the board. A card can be placed at any position, but the cells occupied by cards must not overlap, and they must not be placed on cells that cannot be used. The goal is to make the total number of occupied cells as large as possible.

Little A wants to know: under the optimal placement strategy, what is the maximum number of cells that can be occupied?

Input Format

The first line contains two positive integers $n, m\ (1 \le n, m \le 10)$.

The next $n$ lines each contain a string of length $m$, consisting only of . and #, representing the placement type of each cell on the board.

Output Format

Output one integer, representing the answer.

3 3
...
...
...

9

3 3
..#
.#.
#..

4

Hint

Sample explanation:

In Sample 1, the optimal placement is as follows: using the first and the second card, you can occupy at most $9$ cells.

In Sample 2, the optimal placement is as follows: using the second card, you can occupy at most $4$ cells. Red indicates cells where cards cannot be placed.

Translated by ChatGPT 5