시간이 흐른 지금, Bash에게 한 통의 편지가 왔다. 이는 Windows 왕국의 성, Eight 성을 밖에서 바라본 도면과 Eight 성에 숨겨진 비밀이었다. M×N의 격자에 벽돌로 지어진 Windows 왕국의 성은 최신의 공법을 통해 만들어졌다. 예전에는 벽돌의 무게를 지탱하는 법을 잘 알지 못하였기 때문에 벽돌의 바로 밑에 다른 벽돌이 있어야만 성을 쌓을 수 있었지만, Windows 왕국의 최신 기술에 따르면, 벽돌의 양쪽 밑에 벽돌이 있다면 바로 밑에 벽돌이 없이도 성을 쌓을 수 있게 된 것이다.
즉, 첫 번째 그림과 두 번째 그림의 경우 가능한 벽돌의 배치가 되고, 세 번째의 경우는 불가능한 경우가 되는 것이다.
이를 본 Bash는 무릎을 탁 치며 Cmd에게 복수를 할 준비를 하기 시작하였다. Bash를 도와 외부에서 본 Windows 왕국의 Eight 성 모양이 주어질 때, 성 내부에 존재하는 벽돌의 수의 최소값을 구하는 프로그램을 작성하라.
도면상 가장 아래에는 반드시 2개 이상의 벽돌이 존재하며, 공개된 모든 벽돌은 좌우상하 또는 대각선으로 연결되어 있다. 또한, 도면 상에는 외부에 노출된 벽돌만이 공개된다. 이 공개된 벽돌과 바닥으로 둘러싸인 부분을 내부라 칭한다.
ex)
입력
5 5
0 0 1 0 0
1 1 2 1 1
1 2 2 2 1
1 2 2 2 1
1 2 2 2 1
출력
3