CCTV Blind Spots

An office divided into 1×1 squares forms a rectangle of $N$ rows and $M$ columns. Cameras are installed in the office, and there are five types of camera.

Type 1	Type 2	Type 3	Type 4	Type 5

A type 1 camera watches one direction. Types 2 and 3 watch two directions: the two directions of a type 2 camera are opposite to each other, and the two directions of a type 3 camera are at a right angle. A type 4 camera watches three directions and a type 5 camera watches four.

A camera watches every cell along each of its directions, all the way to the end. The office contains walls, and a camera cannot see through a wall. A cell that no camera watches is a blind spot.

You can rotate a camera. Every rotation is a multiple of 90 degrees, so each watched direction runs along a row or along a column.

On the map, 0 is an empty cell, 6 is a wall, and the digits 1 to 5 give the type of a camera. Look at the map below.

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

Marking the watched cells with # for each direction the type 1 camera can face gives the following.

Facing right:

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

Facing left:

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

Facing up:

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

Facing down:

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

A camera cannot see through a wall, so while the type 1 camera faces right, the cell to the right of the 6 is not watched.

Look at the next map.

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

The four ways of orienting the two type 2 cameras give the following watched cells.

Top left type 2 horizontal, bottom right type 2 horizontal:

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

Top left type 2 horizontal, bottom right type 2 vertical:

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

Top left type 2 vertical, bottom right type 2 horizontal:

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

Top left type 2 vertical, bottom right type 2 vertical:

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

A camera sees past a cell that holds another camera. Look at the map below.

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

If the type 2 camera watches vertically and the type 3 camera watches left and down, the watched cells are these.

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

You are given the size of the office, its contents, and the cameras in it. Write a program that chooses the direction of every camera so that the number of blind spots is as small as possible, then prints that number.

The first line contains the height $N$ and the width $M$ of the office. ($1 \le N, M \le 8$)

Each of the next $N$ lines describes one row of the office. 0 is an empty cell, 6 is a wall, and the digits 1 to 5 are cameras of the types described above. The $M$ values on a line are separated by spaces.

The office holds at most 8 cameras.

Print the smallest possible number of blind spots on the first line.