Se dă o matrice A cu N linii și M coloane, cu valori cuprinse între 1 și N∙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 ] ≥ A[ i ][ j – 1], pentru orice pereche (i, j) cu 1 ≤ i ≤ N și 2 ≤ j ≤ M și A[ i ][ j ] ≥ A[ i – 1][ j ], pentru orice pereche (i, j) cu 2 ≤ i ≤ N și 1 ≤ j ≤ M.

Cerința

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 ≤ N, M ≤ 100
• Pentru teste în valoare de 9 puncte: 1 ≤ N, M ≤ 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

Exemplu

yinyang.in

2 3
1 2 4
3 5 6

yinyang.out

0

Explicație

Matricea dată este matrice yin-yang.

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:

#include <bits/stdc++.h>
using namespace std;

ifstream cin("yinyang.in");
ofstream cout("yinyang.out");

int n , m , a[101][101] , cnt , ok;

int swaplinii(int x , int y)
{
    for(int i = 1 ; i <= m ; i++)
        swap(a[x][i] , a[y][i]);
}

int swapcol(int x , int y)
{
    for(int i = 1 ; i <= n ; i++)
        swap(a[i][x] , a[i][y]);
}
int main()
{
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
            cin >> a[i][j];
    for(int k = 1 ; k <= m ; k++)
    {
        for(int i = 1 ; i <= n ; i++)
            for(int j = 2 ; j <= m  ; j++)
                if(a[i][j] < a[i][j - 1])
                    swapcol(j , j - 1) , cnt++;
    }
    for(int k = 1 ; k <= n ; k++)
    {
        for(int i = 2 ; i <= n ; i++)
            for(int j = 1 ; j <= m  ; j++)
                if(a[i][j] < a[i-1][j])
                    swaplinii(i , i - 1) , cnt++;
    }
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 1 ; j <= m ; j++)
            if(a[i][j] < a[i][j - 1] || a[i][j] < a[i - 1][j]) ok = 1;
    }
    if(ok == 0) cout << cnt;
    else cout << -1;
}