왕궁의 경비병

어느 왕국에 왕과 그의 성이 있었다. 성의 평면도는 $M \times N$개의 단위 정사각형으로 나뉜 직사각형이다. 각 칸은 벽이거나 비어 있으며, 비어 있는 칸을 방이라고 부른다. 매우 의심이 많은 왕은 어느 날 몇몇 방의 바닥에 (바닥에 악어가 있는) 함정을 파 두었다.

왕은 성 안에 가능한 한 많은 경비병을 배치하려고 한다. 경비병은 누군가를 보는 즉시 총을 쏘도록 훈련되어 있어서, 두 경비병이 서로를 보게 되면 서로에게 총을 쏘고 만다. 또한 함정이 있는 방에는 경비병을 둘 수 없다.

각 경비병은 체스의 룩처럼 상·하·좌·우 네 방향만 볼 수 있다. 한 방에는 경비병을 최대 한 명만 둘 수 있다. 서로 다른 두 방에 있는 두 경비병은, 두 방이 같은 행 또는 같은 열에 있고 그 사이에 벽이 하나도 없을 때에만 서로를 본다. (함정은 시야를 가리지 않는다.)

이 규칙을 지키면서 왕이 성 안에 배치할 수 있는 경비병의 최대 수를 구하여라.

첫째 줄에 성 평면도의 크기를 나타내는 두 정수 $M$, $N$ ($1 \le M, N \le 200$)이 주어진다. 이어지는 $M$개의 줄 중 $i$번째 줄에는 공백 하나로 구분된 $N$개의 정수 $a_{i,1}, \dots, a_{i,N}$이 주어지며, 각 값의 의미는 다음과 같다.

• $a_{i,j} = 0$: 칸 $[i, j]$가 비어 있음 (함정이 없는 방)
• $a_{i,j} = 1$: 칸 $[i, j]$에 함정이 있음
• $a_{i,j} = 2$: 칸 $[i, j]$가 벽임

칸의 첫 번째 좌표는 행, 두 번째 좌표는 열이다.

성 안에 배치할 수 있는 경비병의 최대 수 $K$를 한 줄에 출력한다.

위 예시에 해당하는 성과, 경비병 수가 최대가 되는 배치 하나를 나타낸 그림이다.