CCTV 사각지대

한 사무실을 1×1 크기의 정사각형 칸으로 나누면 세로 $N$칸, 가로 $M$칸의 직사각형이 된다. 이 사무실에는 CCTV가 설치되어 있고, CCTV의 종류는 다섯 가지다.

1번	2번	3번	4번	5번

1번 CCTV는 한 방향만 감시한다. 2번과 3번은 두 방향을 감시하는데, 2번은 두 방향이 서로 반대여야 하고 3번은 두 방향이 직각을 이뤄야 한다. 4번은 세 방향을, 5번은 네 방향을 감시한다.

CCTV는 감시하는 방향에 놓인 칸을 끝까지 감시한다. 사무실에는 벽이 있고, CCTV는 벽을 통과하지 못한다. 어떤 CCTV도 감시하지 못하는 칸을 사각지대라고 한다.

CCTV는 회전시킬 수 있다. 회전은 항상 90도 단위이며, 감시하는 방향은 가로 또는 세로여야 한다.

지도에서 0은 빈 칸, 6은 벽, 1부터 5까지의 숫자는 CCTV의 종류 번호다. 아래 지도를 보자.

0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 0 0 0 0

1번 CCTV가 보는 방향에 따라 감시받는 칸을 #로 표시하면 다음과 같다.

오른쪽을 볼 때:

0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 # 6 0
0 0 0 0 0 0

왼쪽을 볼 때:

0 0 0 0 0 0
0 0 0 0 0 0
# # 1 0 6 0
0 0 0 0 0 0

위쪽을 볼 때:

0 0 # 0 0 0
0 0 # 0 0 0
0 0 1 0 6 0
0 0 0 0 0 0

아래쪽을 볼 때:

0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 # 0 0 0

CCTV는 벽을 통과하지 못하므로, 1번이 오른쪽을 감시할 때 6의 오른쪽 칸은 감시받지 않는다.

다음 지도를 보자.

0 0 0 0 0 0
0 2 0 0 0 0
0 0 0 0 6 0
0 6 0 0 2 0
0 0 0 0 0 0
0 0 0 0 0 5

두 2번 CCTV의 방향을 정하는 네 가지 경우에 감시받는 칸은 아래와 같다.

왼쪽 위 2번이 가로, 오른쪽 아래 2번이 가로:

0 0 0 0 0 #
# 2 # # # #
0 0 0 0 6 #
0 6 # # 2 #
0 0 0 0 0 #
# # # # # 5

왼쪽 위 2번이 가로, 오른쪽 아래 2번이 세로:

0 0 0 0 0 #
# 2 # # # #
0 0 0 0 6 #
0 6 0 0 2 #
0 0 0 0 # #
# # # # # 5

왼쪽 위 2번이 세로, 오른쪽 아래 2번이 가로:

0 # 0 0 0 #
0 2 0 0 0 #
0 # 0 0 6 #
0 6 # # 2 #
0 0 0 0 0 #
# # # # # 5

왼쪽 위 2번이 세로, 오른쪽 아래 2번이 세로:

0 # 0 0 0 #
0 2 0 0 0 #
0 # 0 0 6 #
0 6 0 0 2 #
0 0 0 0 # #
# # # # # 5

CCTV는 다른 CCTV가 놓인 칸을 통과해서 그 너머까지 감시한다. 아래 지도를 보자.

0 0 2 0 3
0 6 0 0 0
0 0 6 6 0
0 0 0 0 0

2번이 세로를 감시하고 3번이 왼쪽과 아래쪽을 감시하면 감시받는 칸은 다음과 같다.

# # 2 # 3
0 6 # 0 #
0 0 6 6 #
0 0 0 0 #

사무실의 크기와 상태, 그리고 CCTV의 정보가 주어진다. CCTV의 방향을 적절히 정해서 사각지대의 최소 크기를 구하는 프로그램을 작성하시오.

첫째 줄에 사무실의 세로 크기 $N$과 가로 크기 $M$이 주어진다. ($1 \le N, M \le 8$)

둘째 줄부터 $N$개의 줄에 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1부터 5까지의 숫자는 문제에서 설명한 종류의 CCTV다. 한 줄에 놓인 $M$개의 값은 공백으로 구분된다.

CCTV의 개수는 8개를 넘지 않는다.

첫째 줄에 사각지대의 최소 크기를 출력한다.