* $1 ≤ N, K ≤ 100.000$
* Elementele matricii $A$ sunt numere naturale mai mici sau egale cu $1000$.
* Matricea $A$ nu va fi neaparat simetrica fata de diagonala principala.

* Orice camera $i$ apare in cel mult una din cele $K$ inversari.
* Nu exista doua inversari $(a,b)$ si $(c,d)$, $a &le; b$, $c &le; d$, astfel incat $c > a$, $c < b$ si $b < d$.

* Orice camera $i$ apare cel mult o data in cele $K$ inversari.
* Nu exista doua inversari $(a,b)$ si $(c,d)$ cu $c > a$, $c < b$ si $b < d$.

h2. Exemplu
table(example). |_. papuci.in |_. papuci.out |

| 6 3

| 6 2

abccba
1 2 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 5 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 6
4 5

3 3

| 19
|
h3. Explicatie

Timpul maxim $19$ se obtine interschimband papucii din camerele $4$ si $5$. Asadar, sirul de papuci inainte de inceperea vizitei in muzeu este $abcbca$.

Timpul maxim $19$ se obtine interschimband papucii din camerele $4$ si $5$, rezultand sirul de papuci $abcbca$.

== include(page="template/taskfooter" task_id="papuci") ==

3569