빵집

제빵사 원웅이는 가스비를 줄이기 위해 근처 가스관에서 자신의 빵집까지 파이프라인을 설치하려고 한다. 빵집 주변은 R x C 격자로 표현한다. 첫 번째 열은 근처 가스관이고, 마지막 열은 원웅이의 빵집이다.

각 칸은 빈 칸이거나 건물이 있는 칸이다. 건물이 있는 칸에는 파이프를 놓을 수 없다.

파이프라인은 반드시 첫 번째 열의 한 칸에서 시작해 마지막 열의 한 칸에서 끝나야 한다. 한 칸에서는 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선에 있는 칸으로만 이어 갈 수 있으며, 연결은 각 칸의 중심을 잇는 방식이다.

원웅이는 가능한 한 많은 파이프라인을 설치하려고 한다. 서로 다른 파이프라인은 같은 칸을 지날 수 없다. 격자가 주어졌을 때 설치할 수 있는 파이프라인의 최대 개수를 구하라.

첫째 줄에 R과 C가 주어진다. (1 <= R <= 10,000, 5 <= C <= 500)

다음 R개 줄에는 빵집 주변의 격자가 주어진다. .는 빈 칸, x는 건물이 있는 칸을 뜻한다. 첫 번째 열과 마지막 열은 항상 빈 칸이다.

첫째 줄에 설치할 수 있는 파이프라인의 최대 개수를 출력한다.