Scribbling Witch

The witch ALBERTINE is drawing graffiti at the entrance of a rectangular barrier made of square cells, with $W$ columns and $H$ rows. In this world, graffiti is made by painting every cell either white or black.

Her familiar ANJA has already drawn part of the graffiti. The witch wants to paint all the remaining cells and complete it. She has one condition.

• Two different cells are called adjacent if they share an edge. In a finished graffiti, for any two black cells, there must be exactly one path from one to the other that follows adjacent black cells.
• No two white cells may be adjacent.

The witch likes black, so she wants a finished graffiti that meets the condition and has as many black cells as possible. What is the maximum number of black cells in a graffiti that satisfies her condition?

H W
c11c12…c1W
c21c22…c2W
…
cH1cH2…cHW

$H$ is the height of the barrier and $W$ is its width.

$c_{ij}$ is the state of the cell in row $i$ from the top and column $j$ from the left. If the cell is painted black, $c_{ij}$ is '#'. If it is painted white, $c_{ij}$ is '.'. If it is not yet painted, $c_{ij}$ is '?'.

Print the maximum possible number of black cells in one line, when the condition is satisfied.

If there is no way to paint the graffiti that satisfies the condition, print -1.

• $1 \le H \le 11$
• $1 \le W \le 11$
• Each $c_{ij}$ is one of '#', '.', or '?'.