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

Dupa multi ani de cand isi doreste acest lucru, Ionel are in sfarsit ocazia sa viziteze muzeul X. Ca orice vizitator, Ionel trebuie sa respecte regulamentul muzeului, astfel ca ghidul i-l explica la intrare. Baiatul va vizita cele $N$ camere ale muzeului in ordine, de la camera $1$ la camera $N$. In prima camera, va incalta o pereche de papuci (proprietarii muzeului vor sa protejeze astfel covoarele de o inestimabila valoare), iar in fiecare din camerele urmatoare va da jos perechea de papuci curenta si va lua alta pereche pe care o va purta doar in camera respectiva. Papucii sunt de $26$ de tipuri (etichetate cu literele de la $'a'$ la $'z'$), iar fiecare camera a muzeului dispune de o pereche dintr-unul din aceste tipuri. Timpul in care Ionel da jos papucii de tipul $i$ si incalta papucii de tipul $j$ este dat de elementul $A[i][j]$ al unei matrice $A$ furnizate la intrarea in muzeu.

De ceva timp, Ionel isi doreste sa viziteze muzeul X, iar astazi tocmai s-a ivit aceasta ocazie. Ca orice vizitator, va trebui, insa, sa respecte regulamentul muzeului, astfel ca ghidul i-l explica la intrare. Baiatul va vizita cele $N$ camere ale muzeului in ordine, de la camera $1$ la camera $N$. In prima camera, va incalta o pereche de papuci (proprietarii muzeului vor sa protejeze astfel covoarele de o inestimabila valoare), iar in fiecare din camerele urmatoare va da jos perechea de papuci curenta si va lua alta pereche pe care o va purta doar in camera respectiva. Papucii sunt de $26$ de tipuri (etichetate cu literele de la $'a'$ la $'z'$), iar fiecare camera a muzeului dispune de o pereche dintr-unul din aceste tipuri. Timpul in care Ionel da jos papucii de tipul $i$ si incalta papucii de tipul $j$ este dat de elementul $A[i][j]$ al unei matrice patratice $A$ furnizate la intrarea in muzeu.

Baiatul isi doreste o vizita cat mai lunga in muzeu, de aceea ghidul ii prezinta Regula Vizitatorilor Speciali. El primeste o lista de $K$ perechi de camere $(a, b)$ si poate decide pana sa isi inceapa vizita ce perechi sa aleaga dintre acestea si sa inlocuiasca papucii din camera $a$ cu papucii din camera $b$ si invers. Apoi se va bucura de vizita si va profita de timpul cat schimba papucii punand cat mai multe intrebari ghidului.

Baiatul isi doreste o vizita cat mai lunga in muzeu, de aceea ghidul ii prezinta Regula Vizitatorilor Speciali. Ionel primeste o lista de $K$ perechi $(a, b)$ de camere. Pentru fiecare din acestea, el trebuie sa decida, inainte sa-si inceapa vizita in muzeu, daca solicita inversarea papucilor din camera $a$ cu cei din camera $b$ sau nu. Apoi se va bucura de vizita si va profita de timpul cat schimba papucii intre doua camere consecutive, punand cat mai multe intrebari ghidului.

h2. Date de intrare

Pe prima linie a fisierului de intrare $papuci.in$ se vor afla $N$ si $K$, reprezentand numarul de camere ale muzeului, respectiv numarul de schimburi de papuci intre camere. Pe linia a doua se va afla un sir de $N$ litere mici ale alfabetului englez, astfel incat al $i$-lea caracter sa reprezinte tipul initial de papuci din camera $i$. Pe urmatoarele $26$ de linii se vor afla cate $26$ de numere reprezentand matricea $A$ ($A[i][j]$ = timpul de care are nevoie Ionel pentru a descalta papucii de tipul $i$ si a incalta papucii de tipul $j$). Pe fiecare din urmatoarele $K$ linii se va afla cate o pereche de numere $a b$ ($a ≤ b$), despartite printr-un spatiu, reprezentand un schimb posibil de papuci intre camerele $a$ si $b$.

Pe prima linie a fisierului de intrare $papuci.in$ se vor afla numerele $N$ si $K$ cu semnificatiile de mai sus. Pe linia a doua se va afla un sir de $N$ litere mici ale alfabetului englez, astfel incat al $i$-lea caracter sa reprezinte tipul initial de papuci din camera $i$. Pe urmatoarele $26$ de linii se vor afla cate $26$ de numere naturale reprezentand matricea $A$ ({$A[i][j]$} = timpul de care are nevoie Ionel pentru a descalta papucii de tipul $i$ si a incalta papucii de tipul $j$). Pe fiecare din urmatoarele $K$ linii se vor afla cate 2 numere $a$ si $b$, {$1 ≤ a ≤ b ≤ N$}, reprezentand o inversare de papuci pe care Ionel o poate face intre camerele $a$ si $b$ inainte de a-si incepe vizita.

h2. Date de iesire

In fisierul de iesire $papuci.out$ se vor scrie pe prima linie 2 numere $X$ si $Y$ reprezentand timpul maxim obtinut de Ionel la schimbarea papucilor, respectiv numarul de schimburi intre camere necesare obtinerii acestui timp $X$. Pe urmatoarea linie se vor scrie $Y$ numere distincte intre $1$ si $K$ bla bla bla

Pe prima linie a fisierului de iesire $papuci.out$ se va scrie timpul maxim obtinut de Ionel doar din descaltarea si incaltarea perechilor de papuci la trecerea dintr-o camera intr-alta pe parcursul intregii vizite.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $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$.

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

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

| 6 3
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
2 3 1 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
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 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 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 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 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 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 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 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 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 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 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 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$.

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

3569