16726번 - 영과일 학회방

문제

영과일은 학회방이 없어질 위기에 처했지만 우수한 학회원들의 실력을 인정받아 학회방을 다시 배정 받을 수 있었다! 이에 행복해진 영과일 총무부장 재현이는 새로운 마음으로 1 × 2, 1 × 1 타일을 구매하여 학회방 바닥을 모두 덮으려고 한다.

알뜰한 재현이를 도와 학회방 도면이 주어졌을 때 학회방 바닥을 모두 덮을 수 있는 최소의 타일 개수를 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에 학회방 도면의 행의 수를 나타내는 N(1 ≤ N ≤ 50)과 열의 수를 나타내는 M(1 ≤ M ≤ 50)이 주어진다.

두 번째 줄부터 N개의 줄에 학회방 도면의 정보를 나타내는 길이가 M인 문자열이 주어진다. i+1번째 줄의 j번째 문자가 ‘.’ 일 경우 바닥, ‘X’ 일 경우 기둥을 나타낸다.

출력

첫 번째 줄에 필요한 타일의 최소 개수를 출력한다.

제한

힌트