갤러리

갤러리 지도는 M×N개의 정사각형 칸으로 이루어진 격자이다. 각 칸은 벽(X)이거나 빈 공간(.)이다. 벽은 회색, 빈 공간은 흰색으로 생각할 수 있다.

벽에 그림을 걸려고 한다. 그림 하나의 길이는 격자 칸 한 변 길이의 두 배이다. 그림은 빈 공간과 맞닿아 있는 벽면에만 걸 수 있고, 같은 벽면 위에서 그림끼리 겹쳐서는 안 된다. 갤러리 지도가 주어질 때, 걸 수 있는 그림의 최대 개수를 구하시오.

첫째 줄에 갤러리의 세로 길이 M과 가로 길이 N이 주어진다. (1 ≤ M, N ≤ 1,000) 이어지는 M개의 줄에는 길이 N의 문자열이 하나씩 주어진다. 각 문자는 X 또는 .이며, X는 벽을, .은 빈 공간을 뜻한다.

모든 입력에서 첫 행과 마지막 행, 첫 열과 마지막 열은 모두 벽이다.

걸 수 있는 그림의 최대 개수를 출력한다.