h2. Date de intrare

Pe prima linie a fisierului de intrare $papuci.in$ se vor afla $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 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$, {$a ≤ b$}, reprezentand un schimb de papuci pe care Ionel il poate face intre camerele $a$ si $b$ inainte de a-si incepe vizita.

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 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$, {$a ≤ b$}, reprezentand un schimb de papuci pe care Ionel il 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 din cele $K$, necesare obtinerii acestui timp $X$. Pe urmatoarea linie se vor scrie numerele de ordine ale celor $Y$ schimburi folosite de Ionel (schimburile sunt numerotate de la $1$ la $K$ in ordinea in care apar in fisierul de intrare).

Pe prima linie a fisierului de iesire $papuci.out$ se vor scrie 2 numere $X$ si $Y$ reprezentand timpul maxim obtinut de Ionel la schimbarea papucilor, respectiv numarul de schimburi alese din cele $K$ pentru a obtine o solutie cu timpul $X$. Pe urmatoarea linie se vor scrie $Y$ numere de ordine distincte ale schimburilor folosite de Ionel (schimburile sunt numerotate de la $1$ la $K$ in ordinea in care apar in fisierul de intrare).

h2. Restrictii

* Matricea $A$ nu va fi neaparat simetrica fata de diagonala principala.
* Orice camera $i$ apare cel mult o data in cele $K$ schimburi.
* Nu exista doua schimburi $(a,b)$ si $(c,d)$ cu $c > a$, $c < b$ si $b < d$ (altfel spus, perechile nu se intersecteaza)

* Schimburile trecute in fisierul de iesire trebuie sa fie distincte (un schimb nu va fi trecut de mai multe ori).

* Orice solutie care furnizeaza timpul maxim este considerata corecta.

h2. Exemplu