There was once a popular game called Infinity Loop. Here is a brief introduction to the game:

The game is played on an $n \times m$ grid-like board. Some cells contain pipes, which may have ports at the midpoints of the cell boundaries. All pipes have the same thickness, so if two adjacent cells both have ports at their common boundary, those ports are considered connected. There are 15 types of pipe shapes:

At the start of the game, there may be leaks on the board.

Formally: If there exists a port that is not connected to any other port, it is considered a leak.

Players can perform an operation: select a cell containing a non-straight pipe and rotate the pipe 90 degrees clockwise or counter-clockwise around the center of the cell.

Straight pipes refer to the two types of pipes in the middle row of the left image.

Given an initial configuration, what is the minimum number of operations required to ensure there are no leaks on the board?

Input

The first line contains two positive integers $n$ and $m$, representing the size of the grid.

The next $n$ lines each contain $m$ integers. Each number is in the range $[0, 15]$ and can be viewed as a 4-bit binary number. From the lowest bit to the highest bit, they represent whether there are pipe ports in the up, right, down, and left directions, respectively, in the initial configuration.

Specifically, if the number is $0$, it means there is no pipe at that position.

For example, $3(0011_{(2)})$ represents ports at the top and right, which is an L-shape, while $12(1100_{(2)})$ represents ports at the bottom and left, which is an L-shape rotated by 180 degrees.

Output

Output a single line representing the minimum number of operations. If it is impossible to achieve the goal, output -1.

Examples

Input 1

2 3
3 14 12
3 11 12

Output 1

2

Note 1

The board for Example 1 is as follows:

The rotation method is straightforward. First, rotate the pipe in the top-left dashed cell 90 degrees clockwise:

Then, rotate the pipe in the bottom-right dashed cell 90 degrees clockwise, which seals the pipes.

Input 2

3 2
1 8
5 10
2 4

Output 2

-1

Note 2

Example 2 corresponds to the first image in the problem description; it is impossible to achieve the goal.

Input 3

3 3
9 11 3
13 15 7
12 14 6

Output 3

16

Note 3

Example 3 corresponds to the second image in the problem description. Rotating the pipes in every cell except the center cell by 180 degrees solves the puzzle.

Constraints