시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 22 13 9 81.818%

문제

동혁이는 직사각형 체스판을 가지고 있다. 체스판의 행과 열은 0번부터 시작한다. i행 j열의 색은 i+j가 짝수이면 검정색, 홀수이면 흰색이다. 체스판의 일부 칸에는 말이 놓여져 있다.

윤호는 L-모양으로 생긴 타일을 매우 많이 가지고 있다. 타일은 체스판의 한 칸 크기와 같은 정사각형을 아래 그림처럼 3개를 이어 붙인 형태이다.

OO
O

윤호는 동혁이의 체스판에 다음 조건을 만족시키면서 타일을 체스판 위에 올려 놓으려고 한다.

  • 모든 타일은 회전 시킬 수 있다. (90, 180, 270도)
  • 모든 타일은 체스판 위의 세 칸을 덮어야 한다.
  • 타일은 겹치면 안된다.
  • 말이 이미 올려져있는 칸은 타일이 덮을 수 없다.
  • 타일의 꼭지점 칸(두 정사각형과 붙어있는 칸)은 체스판의 검정 칸을 덮어야 한다.

윤호가 놓을 수 있는 타일의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 체스판의 행의 크기 R과 열의 크기 C가 주어진다. (1 ≤ R ≤ 47, 1 ≤ C ≤ 47)

둘째 줄부터 R개의 줄에 체스판의 상태가 주어진다. 'X'는 말이 놓여져 있는 상태, '.'는 빈 칸이다.

출력

윤호가 놓을 수 있는 타일의 최대 개수를 출력한다.

예제 입력

3 3
X.X
...
X.X

예제 출력

1

예제 입력 2

3 3
...
...
...

예제 출력 2

2

예제 입력 3

1 19
......X.X.XXX.X.XX.

예제 출력 3

0

예제 입력 4

4 38
X.....XXX.XX..XXXXXXXXX...X.XX.XX....X
.XXXX..X..XXXXXXXX....XX.X.X.X.....XXX
....XX....X.XX..X.X...XX.X..XXXXXXX..X
XX.XXXXX.X.X..X..XX.XXX..XX...XXX.X...

예제 출력 4

13

힌트