yinyang

Se dă o matrice $A$ cu $N$ linii și $M$ coloane, cu valori cuprinse între $1$ și $N \cdot M$ inclusiv, nu neapărat distincte. O operație constă în selectarea a două linii sau două coloane consecutive și interschimbarea acestora (swap). O matrice yin-yang este o matrice în care $A[i][j] \geq A[i][j – 1]$, pentru orice pereche $(i, j)$ cu $1 \leq i \leq N$ și $2 \leq j \leq M$ și $A[i][j] \geq A[i – 1][j]$, pentru orice pereche $(i, j)$ cu $2 \leq i \leq N$ și $1 \leq j \leq M$.

Cerinţă

Să se determine numărul minim de operații necesare pentru a transforma matricea dată într-o matrice yin-yang.

Date de intrare

În fișierul de intrare yinyang.in se află scrise pe prima linie numerele naturale $N$ și $M$, cu semnificația din enunț. Pe fiecare dintre următoarele $N$ linii se află câte $M$ numere naturale, reprezentând elementele matricei date $A$. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.

Date de ieșire

În fișierul yinyang.out se va scrie numărul minim de operații cerut sau $-1$ dacă nu există soluție.

Restricții și precizări

• $1 \leq N, M \leq 100$;
• Pentru teste în valoare de $9$ puncte: $1 \leq N, M \leq 5$;

• Pentru alte teste în valoare de $18$ puncte: $N = 1$;
• Pentru alte teste în valoare de $36$ de puncte elementele din matrice sunt DISTINCTE.

Exemplul 1

yinyang.in

2 3
1 2 4
3 5 6

yinyang.out

0

Explicație

Matricea dată este matrice yin-yang.

Exemplul 2

yinyang.in

2 3
6 6 5
4 6 2

yinyang.out

3

Explicație

Operațiile pot fi următoarele:

• swap(linia 1, linia 2);
• swap(coloana 2, coloana 3);
• swap(coloana 1, coloana 2).

Matricea dată va ajunge la final în forma yin-yang:

Figura 1 din enunțul original al problemei yinyang.Mărește schema ↗