Cangaroo

방 안에 있는 커다란 문제 하나를 짚고 넘어가자: 당신은 한동안 방에서 캥거루를 키웠고, 이 동물을 계속 데리고 있고 싶기 때문에 의심을 사지 않으면서 숨겨야 한다. 이만한 크기의 동물을 숨기는 일은 어렵다. 공간을 많이 쓰면 친구들에게 뭔가 숨기고 있다는 것이 뻔히 드러난다. 따라서 캥거루를 숨기려면 공간을 최대한 적게 써야 한다.

캥거루를 벽에 세워 두었을 때, 당신은 그 동물의 흑백 사진을 찍었다. 집 안을 둘러보니 캥거루를 숨길 도구로 찾은 것은 빈 깡통뿐이었다. 깡통의 크기는 사진에서 $2 \times 2$ 픽셀에 해당하고, 깡통끼리는 겹칠 수 없다. 그래서 cangaroo를 만들 수 있고, 누군가 캥거루 모양으로 깡통을 쌓아 둔 이유를 묻는다면 그냥 자기 안 좋은 장난이라고 하면 된다.

각 깡통의 위치는 사진의 $2\times 2$ 픽셀 블록과 정확히 일치해야 하며, 일부 픽셀만 덮도록 옮기거나 회전할 수 없다. 또한 깡통은 공중에 떠 있을 수 없으므로, 모든 깡통은 사진의 맨 아래 행 바로 아래에 있는 바닥이나 다른 깡통이 받쳐 주어야 한다. 다른 깡통이 받치는 경우에는 왼쪽 절반과 오른쪽 절반 중 적어도 하나가 그 깡통 위에 바로 놓여야 한다. 구조물은 그 외의 균형을 맞출 필요는 없다.

캥거루를 숨기는 데 필요한 깡통의 최소 개수는 얼마인가?

입력은 다음과 같다.

• 방의 높이와 너비를 나타내는 두 정수 $n$ ($2\leq n\leq 100$)과 $m$ ($2\leq m\leq 10$)이 한 줄에 주어진다. $n$과 $m$은 모두 짝수이다.
• $n$개의 줄이 주어지며, 각 줄에는 '.' 또는 '#'인 $m$개의 문자가 들어 있다. '#'는 깡통으로 가려야 하는 위치를 나타낸다.

방에서 캥거루를 숨기는 데 필요한 $2 \times 2$ 깡통의 최소 개수를 출력한다.