리딕스 큐브

역사상 가장 많이 팔린 장난감은 루빅스 큐브다. 40년 동안 약 3억 5천만 개가 팔렸다. 카자흐스탄의 한 사업가는 이 퍼즐을 더 단순하게 만든 제품으로 같은 성공을 노렸다. 그가 만든 리딕스 큐브는 $1 \times 1$ 칸으로 이루어진 $N \times M$ 직사각형이고, 각 칸은 어떤 색으로 칠해져 있다.

규칙은 간단하다. 한 번의 이동으로 아무 행 하나 또는 아무 열 하나를 원하는 방향으로 한 칸 순환 이동할 수 있다. 행은 왼쪽이나 오른쪽으로, 열은 위나 아래로 옮긴다. 두 번째 행을 오른쪽으로 한 칸 옮기면 다음과 같다.

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

세 번째 열을 위로 한 칸 옮기면 다음과 같다.

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

모든 행이 같은 색 칸으로만 이루어져 있거나 모든 열이 같은 색 칸으로만 이루어져 있으면, 그 배치를 최종 배치라고 한다.

사업가는 판매를 시작하기 전에 퍼즐의 난이도를 가늠하고 싶어 하고, 그 일을 당신에게 맡겼다. 난이도를 재기 위해 규칙을 단순하게 바꾼다. 먼저 열을 몇 개 옮기고(하나도 옮기지 않아도 된다), 그다음에 행을 몇 개 옮긴다(하나도 옮기지 않아도 된다). 이동 한 번은 한 칸만 옮기므로, 어떤 열을 $k$칸 옮기려면 $\min(k, N-k)$번, 어떤 행을 $k$칸 옮기려면 $\min(k, M-k)$번의 이동이 필요하다.

리딕스 큐브 하나의 배치가 주어진다. 단순해진 규칙으로 최종 배치에 도달할 수 있으면, 그 배치의 난이도는 최종 배치에 도달하는 최소 이동 횟수다. 단순해진 규칙으로 최종 배치에 도달할 수 없으면 그 큐브를 초복잡이라고 부르고, 난이도는 100500이다. (원래 규칙으로는 풀릴 수도 있지만, 그쪽은 너무 복잡하다.)

첫째 줄에 두 정수 $N$과 $M$이 주어진다 ($1 \le N, M \le 5$). 다음 $N$개 줄에는 각각 $M$개의 정수가 주어지고, 퍼즐의 배치를 나타낸다. 각 수는 그 칸의 색을 뜻하며 1 이상 100 이하의 정수다. 주어진 배치가 원래 규칙으로 풀린다는 보장도 없다.

주어진 배치의 난이도를 정수 하나로 출력한다.