타일 놓기

영선이는 방 바닥에 타일을 놓으려고 한다. 바닥은 직사각형이며 $1 \times 1$ 크기의 정사각형 칸으로 나누어져 있다. 타일의 크기는 $1 \times k$이고, $k$는 양의 정수이다. 타일은 바닥의 변과 평행하게 놓아야 하며, 타일의 변은 칸의 경계와 일치해야 한다. 타일끼리 겹쳐서 놓을 수는 없다.

방에는 $1 \times 1$ 크기의 기둥이 몇 개 있고, 기둥이 있는 칸에는 타일을 놓을 수 없다.

바닥에 빈 칸이 남지 않도록 타일을 놓을 때 필요한 타일의 최소 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 방의 세로 크기 $N$과 가로 크기 $M$이 주어진다. ($1 \le N, M \le 10$)

둘째 줄부터 $N$개의 줄에 방 바닥의 모양이 한 줄에 $M$개의 문자로 주어진다. .은 빈 칸이고, #은 기둥이 있는 칸이다.

첫째 줄에 방 바닥을 모두 채우는 데 필요한 타일의 최소 개수를 출력한다.