Maximizing Card Coverage

You are given an n × m grid. Each cell is either available (denoted by a .) or blocked (denoted by a #). You have 4 distinct cards, each available exactly once. Each card has a fixed shape (a tetromino) as shown in the figure below. The shapes are:

• I-card: a straight polyomino of 4 cells in a row.
• O-card: a 2 × 2 square.
• T-card: a T-shaped tetromino.
• L-card: an L-shaped tetromino.

A card can be placed on the grid in any position and orientation (rotations and reflections allowed), as long as all its cells:

• are fully within the grid,
• cover only available cells (i.e. cells with a .), and
• do not overlap with cells covered by another card.

Your task is to determine the maximum number of grid cells that can be covered by placing a subset (or all) of the cards optimally. Since each card covers exactly 4 cells, if you place k cards then 4k cells are covered. Note that it might be impossible to place some cards if the board is too small or the obstacles interfere.

For example, if the grid has no obstacles and is large enough, you can place all 4 cards to cover 16 cells. Otherwise, you might be able to place only a few cards. The image below shows the four card shapes (all in \(\LaTeX\) rendered format):

Input and output format are described below.

inputFormat

The first line contains two integers n and m (n, m ≤ 10) – the number of rows and columns of the grid. Each of the next n lines contains a string of length m consisting only of characters . and #, representing the grid.

outputFormat

Output a single integer – the maximum number of cells that can be covered by placing the cards according to the rules. (Since each card covers 4 cells, the answer is always a multiple of 4.)

sample

4 4
....
....
....
....

16