1399: Box Castle

2차원 세계의 Bash는 Unix 왕국의 왕이다. Bash와 이웃나라인 Windows 왕국의 왕 Cmd는 어릴적부터 막역한 사이였다. 하지만 Bash가 왕자였던 시절, Bash는 Cmd에게 자신이 사랑하던 여자를 빼앗겼으며, 이후 둘은 둘도 없는 철전지 원수 지간이 되었다.
시간이 흐른 지금, 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

도면의 크기를 나타내는 M(<=3,000)과 N(<=3,000)이 첫 줄로 주어진다. 이후 M줄에는 도면의 내용이 주어지며, 각 줄은 N개의 0, 1, 또는 2으로 구성되어 있다. 0은 성 외부를 의미하고, 1은 성을 구성하는 벽돌을, 그리고 2은 성 내부를 의미한다.

Eight 성 내부에 존재하는 벽돌의 최소 값을 구하여라. 만약 해당하는 모양의 성이 존재할 수 없을 경우 -1을 출력하여라.