가죽 패턴 변경하기 (심화)

최신 패션 트렌드가 가죽에 세 개의 반점이 있는 가방이라는 것을 파악한 패션 디자이너 미진은 세 개의 반점이 있는 가방들을 전부 구매하였습니다. 하지만 안타깝게도 패션 트렌드는 빠르게 변하는 경향이 있어, 현재 가장 인기 있는 패션은 반점이 딱 한 개만 있는 가방입니다!

미진은 각 가방의 세 개의 반점을 하나로 합쳐 멋있게 만들고 싶어 합니다. 가방의 가죽은 다음과 같은 N x M 문자 그리드로 나타낼 수 있습니다:

................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
..XXX....XXX....

여기서, 각각의 'X'는 반점의 일부를 나타냅니다. 두 개의 'X'가 같은 점에 속하려면 반점들은 수직적 혹은 수평적으로 인접해야 합니다 (대각선으로 인접하는 것은 적용되지 않습니다), 그러므로 위의 그림은 정확히 세 개의 반점을 가지고 있습니다. 미진의 모든 가방들은 정확히 세 개의 반점을 보유하고 있습니다.

미진은 가능한 적은 수의 칠로 세 개의 반점을 하나의 반점으로 합치고 싶어합니다. 위 예시에서, 그녀는 단지 네 개의 새로운 문자에 'X'를 칠함으로써 이것을 할 수 있습니다 (새로운 문자들은 볼 수 있게 '*'로 표시되어 있습니다).

................
..XXXX....XXX...
...XXXX*...XX...
.XXXX..**..XXX..
...*....XXXXX...
..XXX....XXX....

미진이 세 개의 반점을 하나의 큰 점으로 합치기 위해 얼마나 'X'를 새롭게 칠해야 하는지를 결정해주십시오.

• 첫 번째 줄: 두 개의 공백으로 구분된 정수, N과 M (1 <= N,M <= 50).
• 두 번째 줄..1+N 번째 줄 : 각 줄에는 'X'와 '.'으로 이루어진 길이가 M인 문자열이 포함되어 있으며, 이는 가방의 가죽 패턴의 한 행을 지정합니다.

• 첫 번째 줄 : 하나의 단일한 반점을 얻기 위해 입력 패턴에 추가해야 하는 최소한의 새로운 'X' 개수.