6789

Interview

Time limit1sMemory limit1024 MB

Summary

Each cell holds a card 6, 7, 8, or 9; turning a card rotates it (6 and 9 swap, 8 and 7 stay). Find the minimum number of turns so the grid stays the same after a 180-degree rotation, or -1 if impossible.

Level: Medium4 of 10
Topics: Implementation, Greedy, Matrix
Solved: No attempts yet

Problem

Jaehyun likes digits. Among the 10 digits, he likes 6, 7, 8, and 9 the most. So he made a special card set consisting only of 6, 7, 8, and 9.

Jaehyun currently has $N\times M$ cards. He wants to make a magical $N$ by $M$ card matrix. Each row of the matrix must contain $M$ cards. He has already arranged his cards in the shape of an $N$ by $M$ matrix.

Figure 1. Initial state, not point symmetric.

To be a magic matrix, the matrix must be point symmetric. Rotating the matrix 180 degrees must give the original matrix. For example, 8 is point symmetric with itself, and 6 and 9 are point symmetric with each other.

Jaehyun does not want to change the positions of the cards, so his goal is to make the matrix point symmetric by only rotating cards in their original positions.

Figure 2. After rotating two cards, they are point symmetric.

Find the minimum number of cards you have to turn to make a magic matrix.

Input

The first line contains two integers, $N$ and $M$ . ( $1 \le N,\ M \le 500$ )

Each of the next $N$ lines contains a string of $M$ characters which denotes the numbers written in each card. It is guaranteed that each character is one of 6, 7, 8, or 9.

Output

Print the minimum number of cards you have to turn to make a magic matrix in the first line. If it is not possible to make a magic matrix, print "-1". (without quotes)

Examples3

Example 1
Input
```
2 3
676
679
```
Expected output
```
2
```
Example 2
Input
```
3 3
888
888
888
```
Expected output
```
0
```
Example 3
Input
```
1 1
7
```
Expected output
```
-1
```