시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 5 5 5 100.000%

문제

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

영선이의 방에는 기둥이 놓여져 있는데, 기둥의 크기는 1×1 이다. 또, 타일은 기둥이 놓여진 칸에 놓여질 수 없다.

방 바닥에 놓을 수 있는 타일의 최소 개수를 구하는 프로그램을 작성하시오. 이 때, 바닥에 빈 칸이 있으면 안된다.

입력

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

둘째 줄부터 방 바닥의 모양이 주어진다. '.'은 빈 칸, '#'은 기둥이 놓여진 칸이다.

출력

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

예제 입력

5 5
.....
.....
.....
.....
.....

예제 출력

5

예제 입력 2

6 7
.......
.#..##.
.#.....
.#####.
.##..#.
....###

예제 출력 2

7

예제 입력 3

4 4
####
####
####
####

예제 출력 3

0

예제 입력 4

6 6
...#..
##....
#.#...
.#....
..#...
..#..#

예제 출력 4

9

힌트