낙서하는 마녀

낙서 마녀 ALBERTINE은 $W$열 $H$행의 정사각형 셀로 이루어진 직사각형 결계의 입구에 낙서를 하고 있다. 이 세계에서 낙서는 반드시 셀을 흰색 또는 검은색으로 칠해서 완성된다.

사역마 ANJA가 이미 낙서의 일부를 그렸다. 마녀는 나머지 셀을 모두 칠해 낙서를 완성하려 한다. 마녀에게는 다음과 같은 고집이 있다.

• 두 개의 서로 다른 셀이 변을 공유하면 두 셀은 인접한다고 한다. 완성된 낙서에서 임의의 두 검은 셀에 대해, 한쪽에서 다른 쪽으로 인접한 검은 셀을 따라가는 경로가 정확히 하나만 존재해야 한다.
• 서로 인접한 흰 셀은 없어야 한다.

마녀는 검은색을 좋아하므로, 고집을 지키면서 검은 셀이 가장 많은 낙서를 완성하고 싶어 한다. 고집을 만족하는 낙서에서 검은 셀의 최대 개수는 얼마인가.

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

$H$는 결계 입구의 세로 길이, $W$는 가로 길이이다.

$c_{ij}$는 위에서 $i$행, 왼쪽에서 $j$열에 있는 셀의 상태이다. 검은색으로 칠해진 셀은 '#', 흰색으로 칠해진 셀은 '.', 아직 칠하지 않은 셀은 '?'이다.

고집을 만족하면서 검은 셀의 개수가 가질 수 있는 최댓값을 한 줄에 출력한다.

어떻게 칠해도 고집을 만족할 수 없으면 -1을 출력한다.

• $1 \le H \le 11$
• $1 \le W \le 11$
• $c_{ij}$는 '#', '.', '?' 중 하나이다.