Riddick's Cube

Time limit2sMemory limit64 MB

Summary

Find the cheapest column-then-row cyclic shifts that make every row or every column single-colored, or print 100500 when no such shifts exist.

Level: Medium5 of 10
Topics: Brute force, Simulation, Matrix
Solved: No attempts yet

Problem

The most sold toy in history is Rubik's Cube. About 350 million units were sold in 40 years. A businessman from Kazakhstan wanted to repeat that success with a simpler puzzle. His invention, Riddick's Cube, is an $N \times M$ rectangle of $1 \times 1$ cells, and every cell is painted in some color.

The rules are simple. In one move you can cyclically shift any single row or any single column by one cell in either direction. Rows move left or right, columns move up or down. Shifting the second row to the right looks like this.

 1  2  3  4     1  2  3  4
 5  6  7  8 =>  8  5  6  7
 9 10 11 12     9 10 11 12

Shifting the third column up looks like this.

 1  2  3  4     1  2  7  4
 5  6  7  8 =>  5  6 11  8
 9 10 11 12     9 10  3 12

A configuration is final if every row consists of cells of one color, or every column consists of cells of one color.

The businessman wants to estimate how hard his puzzle is before he starts selling it, and he gave that task to you. To estimate the difficulty the rules are simplified: you first shift some columns (possibly none), and after that you shift some rows (possibly none). One move shifts by a single cell, so moving a column by $k$ cells costs $\min(k, N-k)$ moves and moving a row by $k$ cells costs $\min(k, M-k)$ moves.

You are given the configuration of one Riddick's Cube. If a final configuration is reachable under the simplified rules, the complexity of the configuration is the smallest number of moves that reaches a final configuration. If it is not reachable under the simplified rules, the cube is called mega complex and its complexity is 100500. (The puzzle may still be solvable under the normal rules, but that is too complex.)

Input

The first line contains two integers $N$ and $M$ ( $1 \le N, M \le 5$ ). Each of the next $N$ lines contains $M$ integers describing the puzzle. Each number is the color of the corresponding cell and is an integer between 1 and 100. The given configuration is not guaranteed to be solvable even under the normal rules.

Output

Print one integer, the complexity of the given configuration.

Examples2

Example 1
Input
```
2 3
1 2 1
2 3 3
```
Expected output
```
2
```
Example 2
Input
```
2 3
2 2 1
1 2 1
```
Expected output
```
100500
```