rubine

Ali-Baba și cei $N$ hoţi ai săi au descoperit harta unei comori pe o insulă izolată. Se asimilează harta cu un caroiaj de $L \times C$ regiuni ($L$ linii şi $C$ coloane). În fiecare regiune se află un sipet fermecat, în care se găsesc rubine ($0$ sau mai multe), numărul de rubine din fiecare sipet fiind păstrat în elementul corespunzător al caroiajului.

Se stabileşte următorul plan de acţiune:

• deplasarea hoţului se poate face dintr-o regiune într-o altă regiune vecină (o regiune are maxim $8$ regiuni vecine);
• fiecare hoţ pleacă dintr-o anumită regiune, de coordonate date, spre regiunea în care se află Ali-Baba (regiunea din colţul dreapta jos, de coordonate $L$ şi $C$), pe drumul cel mai scurt (lungimea unui drum fiind egală cu numărul regiunilor parcurse);
• la trecerea printr-o regiune hoţul pune într-un sac rubinele existente în sipetul existent acolo;
• dacă există mai multe drumuri de lungime minimă, un hoţ îl va alege pe acela pe care parcurgându-l, reuşeşte să strângă cât mai multe rubine;
• primul hoţ care se deplasează este cel cu numărul de ordine $1$, urmează apoi cel cu numărul de ordine $2$, $3$, ş.a.m.d., iar în timpul deplasării unui hoţ, ceilalţi stau pe loc până ce acesta ajunge la Ali-Baba;
• sipetul fiind fermecat, în locul rubinelor luate de hoţ, apar altele identice, apariţia petrecându-se înaintea plecării fiecărui hoţ din punctul lui de pornire spre Ali-Baba.

Fiecare hoţ a strâns în sacul său un număr de rubine, cunoscut doar de el şi ajunge cu sacul în regiunea lui Ali-Baba. La împărţirea rubinelor apare şi Sindbad Marinarul care vrea o parte din saci. Ali-Baba cunoscând anumite relaţii care există între perechi de hoţi din regiune va trebui să aleagă acele relaţii care să implice repartizarea unui număr minim de saci lui Sindbad.

Se ştie că alegerea unei perechi de hoţi $(i,j)$ implică repartizarea sacului hoţului $j$ din „cauza” lui $i$ în visteria lui Ali-Baba, însă din acest moment nu se mai poate folosi nici o pereche de forma $(j,k)$, hoţul $j$ fiind eliminat.

Cerință

Ajutaţi-l pe Ali-Baba să aleagă ordinea perechilor astfel încât sacii care rămân să fie într-un număr cât mai mic posibil, știind că aceștia-i revin lui Sindbad.

Date de intrare

Fișierul de intrare rubine.in, conţine:

• Pe prima linie dimensiunile caroiajului: valorile lui $L$ și $C$ separate printr-un spațiu;
• Pe următoarele $L$ linii se află câte $C$ valori separate prin spaţiu, reprezentând numărul de rubine din sipetul aflat în regiunea respectivă;
• Pe următoarea linie urmează $N$, numărul de hoţi;
• Pe următoarele $N$ linii se află coordonatele regiunilor (valori separate printr-un spaţiu) în care se află inițial hoții, pe prima linie dintre acestea pentru hoțul unu, pe linia a doua pentru hoțul doi, etc;
• Pe următoarele linii, până la sfârșitul fișierului se află perechile care reprezintă relațiile din problemă.

Date de ieșire

Ieșirea se va face în fișierul rubine.out în formatul următor:

• Pe prima linie se află numărul $T$ de perechi folosite de Ali-Baba, respectându-se cerințele problemei;
• Pe următoarele $T$ linii se află câte patru valori separate două câte două printr-un spaţiu: $i\ {nr}_1\ j\ {nr}_2$, unde $i$ reprezintă prima valoare din pereche (hoțul cu numărul de ordine $i$), ${nr}_1$ reprezintă numărul de rubine adunate de hoțul $i$, $j$ reprezintă al doilea hoț din pereche (hoțul cu numărul de ordine $j$), ${nr}_2$ reprezentând numărul de rubine strânse de hoțul $j$;
• Pe următoarea linie se află numerele de ordine ale hoților ai căror saci au rămas lui Sindbad, valori separate două câte două printr-un spaţiu;
• Pe ultima linie se află suma rubinelor din sacii rămași lui Sindbad.

Restricții și precizări

• $1 \le L,C,N \le 50$
• $0 \le A[i][j] \le 200$
• Întotdeauna există soluții, dacă există mai multe, se va alege una.
• În fiecare regiune, indiferent dacă este punctul de pornire al unui hoț sau regiunea în care se află Ali-Baba, există câte un sipet cu un anumit număr de rubine. Ali-Baba nu cunoaște numărul de rubine din fiecare sac.
• Nu există doi hoți care se află inițial în aceeași regiune.

Exemplu

rubine.in

4 5
1 0 0 0 0
0 1 0 0 0
0 0 1 4 0
0 0 0 1 5
5
1 1
1 5
4 1
2 2
4 4
1 2
1 4
2 5
3 1
4 5

rubine.out

4
2 9 5 6
1 12 2 9
1 12 4 11
3 10 1 12
3
10