발굴 구역 지키기

발굴 현장을 N행 M열의 격자로 나누어 관리한다. 각 칸은 세 가지 상태 중 하나다. 값이 0인 칸은 아직 아무것도 없는 맨땅이다. 값이 1인 칸은 단단한 암반이라 아무것도 지나가지 못한다. 값이 2인 칸은 모래 유입구이며, 이곳에서 모래가 흘러나온다.

모래는 유입구가 있는 칸에서 출발해 상하좌우로 맞닿은 맨땅으로 흘러 들어간다. 한 번 모래가 들어간 칸에서 다시 상하좌우로 번져 나가므로, 유입구와 맨땅으로만 이어진 곳이면 아무리 멀어도 모래가 닿는다. 암반이 있는 칸으로는 흘러 들어가지 못한다. 모래가 들어간 칸은 더 이상 발굴할 수 없다.

발굴을 시작하기 전에 현장 책임자는 콘크리트 블록을 설치할 수 있다. 블록은 맨땅인 칸에만 놓을 수 있으며, 블록을 놓은 칸은 암반과 같아져서 모래가 지나가지 못한다. 블록을 놓은 칸 자체도 발굴할 수 없다. 블록은 더 놓을 수도 덜 놓을 수도 없이 정확히 세 개를 놓아야 한다.

블록을 세 개 놓은 뒤에 모래가 더 갈 곳이 없을 때까지 흘렀다고 하자. 이때 모래가 들어가지 않고 남은 맨땅 칸의 수를 발굴 가능 칸의 수라고 한다. 블록을 가장 잘 놓았을 때 발굴 가능 칸의 수가 최대 몇 개가 되는지 계산하는 프로그램을 작성하여라.

예를 들어 N=3, M=4인 현장이 다음의 표와 같다고 해보자. 각 위치는 (행, 열)로 나타내며, 행과 열의 번호는 1부터 시작한다.

맨땅은 여덟 칸, 암반은 두 칸, 모래 유입구는 두 칸이다. 이때 (1, 2)와 (2, 1)과 (2, 3)의 세 칸에 블록을 놓는다고 해보자. 블록을 놓은 칸을 1로 바꿔 적으면 현장은 다음과 같다.

(1, 1)에 있는 유입구의 상하좌우는 블록 두 개와 격자 밖이라서 모래가 나갈 곳이 없다. (1, 3)에 있는 유입구도 상하좌우가 블록 두 개와 원래 있던 암반이라서 마찬가지다. 따라서 모래는 어느 칸으로도 흘러가지 못한다.

남은 맨땅은 (2, 2)와 (2, 4)와 (3, 1)과 (3, 2)와 (3, 4)로 다섯 칸이고, 모두 발굴할 수 있다. 블록을 다르게 놓아서 다섯 칸보다 많이 남기는 방법은 없다. 따라서 이 예시에서의 정답은 5다.

입출력 예시

예시 1

입력

3 4
2 0 2 1
0 0 0 0
0 0 1 0

출력

5

예시 2

입력

3 3
0 2 1
2 0 2
0 0 0

출력

1

예시 3

입력

4 4
1 2 0 0
0 0 0 1
0 1 0 0
1 0 0 0

출력

8