== include(page="template/taskheader" task_id="trecere") ==
In orasul Ababuribu exista o portiune de sosea speciala de forma dreptunghiulara. Soseaua este formata din $m$ randuri a cate $n$ dale patrate de aceeasi dimensiune. Dalele sunt insa colorate in $n$ culori diferite, codificate prin numere intregi cuprinse intre 1 si $n$. Se stie ca pentru fiecare culoare exista exact $m$ dale colorate cu aceea culoare.
Coordonatele dalelor vor fi date de linia si coloana pe care se gaseste dala, numerotarea randurilor facandu-se de sus in jos incepand cu 1, iar coloanele se numeroteaza de la stanga la dreapta incepand cu 1.
Primarul orasului doreste sa construiasca o trecere de pietoni pe aceasta portiune de sosea. O trecere va fi formata din $m$ dale avand toate aceeasi culoare si aflate vertical una sub alta, de la primul pana la ultimul rand. Astfel dalele care vor forma trecerea vor avea coordonatele de forma (1,$c$), (2,$c$), (3,$c$),..., ($m$,$c$), unde $c$ este coloana pe care este construita trecerea.
Pentru a construi trecerea, primarul da voie constructorilor sa aleaga culoarea (din cele $n$ disponibile) pe care o va avea trecerea de pietoni precum si coloana pe care se va construi trecerea. De asemenea constructorii au voie sa schimbe intre ele dalele de pe sosea, insa efortul total va trebui sa fie cat mai mic posibil. Efortul schimbarii intre ele a doua dale de coordonatele ($x$, $y$) si respectiv ($x1$,$y1$) este egal cu |$x1$ - $x$| + |$y1$ - $y$|, unde prin |$a$| s-a notat valoarea absoluta a valorii $a$.
De exemplu pentru soseaua din figura alaturata, cea mai eficienta solutie este construirea unei treceri de culoare 1, pe coloana 6.
Efortul construirii acestei sosele este 5. Se vor efectua urmatoarele schimbari: dala (1,6) cu dala (1,7), dala (2,5) cu dala (3,6), dala (3,7) cu dala (4,6).
In orasul Ababuribu exista o portiune de sosea speciala de forma dreptunghiulara. Soseaua este formata din $m$ randuri a cate $n$ dale patrate de aceeasi dimensiune. Dalele sunt insa colorate in $n$ culori diferite, codificate prin numere intregi cuprinse intre 1 si $n$. Se stie ca pentru fiecare culoare exista exact $m$ dale colorate cu aceea culoare. Coordonatele dalelor vor fi date de linia si coloana pe care se gaseste dala, numerotarea randurilor facandu-se de sus in jos incepand cu 1, iar coloanele se numeroteaza de la stanga la dreapta incepand cu {$1$}.
Primarul orasului doreste sa construiasca o trecere de pietoni pe aceasta portiune de sosea. O trecere va fi formata din $m$ dale avand toate aceeasi culoare si aflate vertical una sub alta, de la primul pana la ultimul rand. Astfel dalele care vor forma trecerea vor avea coordonatele de forma ({$1,c$}), ({$2,c$}), ({$3,c$}),..., ({$m$},{$c$}), unde $c$ este coloana pe care este construita trecerea.
Pentru a construi trecerea, primarul da voie constructorilor sa aleaga culoarea (din cele $n$ disponibile) pe care o va avea trecerea de pietoni precum si coloana pe care se va construi trecerea. De asemenea constructorii au voie sa schimbe intre ele dalele de pe sosea, insa efortul total va trebui sa fie cat mai mic posibil. Efortul schimbarii intre ele a doua dale de coordonatele ({$x$}, {$y$}) si respectiv ({$x{~1~}$},{$y{~1~}$}) este egal cu |{$x{~1~}$} - {$x$}| + |{$y{~1~}$} - {$y$}|, unde prin |{$a$}| s-a notat valoarea absoluta a valorii {$a$}.
!>problema/trecere?trecere.gif!
De exemplu pentru soseaua din figura alaturata, cea mai eficienta solutie este construirea unei treceri de culoare {$1$}, pe coloana {$6$}. Efortul construirii acestei sosele este {$5$}. Se vor efectua urmatoarele schimbari: dala ({$1,6$}) cu dala ({$1,7$}), dala ({$2,5$}) cu dala ({$3,6$}), dala ({$3,7$}) cu dala ({$4,6$}).
Daca exista mai multe solutii care implica acelasi efort minim, primarul prefera acea culoare avand cel mai mic cod, iar daca pentru aceasta culoare se pot construi cu acelasi efort minim, mai multe treceri, el va prefera cea mai din stanga trecere.
h2. Cerinta
h2. Date de intrare
Fisierul de intrare $trecere.in$ contine pe prima linie doua numere naturale m si n separate printr-un spatiu, reprezentand numarul de linii respectiv de coloane ale soselei. Urmatoarele m linii ale fisierului vor contine cate $n$ numere naturale cuprinse intre 1 si $n$ (inclusiv) separate prin cate un spatiu, reprezentand culorile dalelor de pe sosea.
Fisierul de intrare $trecere.in$ contine pe prima linie doua numere naturale $m$ si $n$ separate printr-un spatiu, reprezentand numarul de linii respectiv de coloane ale soselei. Urmatoarele $m$ linii ale fisierului vor contine cate $n$ numere naturale cuprinse intre 1 si $n$ (inclusiv) separate prin cate un spatiu, reprezentand culorile dalelor de pe sosea.
h2. Date de iesire
