In lumea World of Warcraft este foarte importanta comunicarea intre cele M cele mai puternice aliante. Periodic cate un reprezentant din fiecare alianta trebuie sa mearga la o intalnire super ultra mega secreta unde se decide ce vor face in viitor.
Fiindu-le incomod sa calatoreasca distante lungi pe jos, ei ar vrea sa se intalneasca intr-un loc in care suma distantelor parcurse de reprezentanti sa fie minima.
Jucatorii de WoW stiu urmatoarele lucruri despre lumea jocului:

• Lumea este reprezentata ca o matrice cu N linii si P coloane.
• Pozitia fiecarui membru reprezentant al aliantelor este cunoscuta.
• In lumea lor sunt locuri periculoase marcate cu 1 in matricea care reprezinta lumea jocului, iar cele sigure sunt marcate cu 0.
• Reprezentantii se pot deplasa in una dintre directiile sus, jos, stanga si dreapta dar nu pot merge intr-un loc periculos. O astfel de deplasare are distanta 1.

Avand la dispozitie toate aceste informatii, ei tot nu pot calcula un loc de intalnire care sa indeplineasca conditiile. Tu poti?

Cerinţă

Scrieti un program care sa determine un loc pentru intalnire L=(X, Y) cu proprietatea ca suma distantelor parcurse de reprezentanti pentru a ajunge la el este minima. De asemenea programul trebuie sa calculeze si suma distantelor parcurse de reprezentanti pana la punctul L.

Date de intrare

Fisierul de intrare wow.in contine pe prima linie 3 numere naturale N P M reprezentand numarul de linii, numarul de coloane ale matricei si respectiv numarul de reprezentanti ai aliantelor. Pe urmatoarele N linii sunt cate P valori de 1 si 0 reprezentand elementele matricei (1 indicand zonele periculoase, iar 0 pe cele sigure). Pe urmatoarele M linii sunt perechi de numere (X, Y) reprezentand locurile curente ale reprezentantilor. Valorile scrise pe aceeasi linie sunt separate prin spatiu. Perechea (0, 0) reprezinta coltul din stanga sus al matricei, iar perechea (N-1, P-1) coltul din dreapta jos.

Date de ieşire

Fisierul de iesire wow.out va contine pe prima linie un numar care reprezinta suma distantelor parcurse de reprezentanti pana la punctul L. A doua linie va contine doua numere X si Y separate prin spatiu, reprezentand linia, respectiv coloana punctului L.
Daca sunt mai multe puncte care satisfac proprietatea lui L se va afisa cel mai mic lexicografic (cel care are X minim, iar daca sunt mai multe cu acelasi X minim, acela dintre acestea care are Y minim).

Restricţii

• 2 <= N, P <= 100
• 2 <= M <= 1500
• 0<= X < N
• 0 <= Y < P
• Pentru datele de test, exista cel putin un loc in care se pot intalni toti reprezentantii.
• Pentru 30% dintre teste, M va avea valoarea 2.

Exemple

wow.in	wow.out	Explicatii
5 5 3 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 4 0	7 3 0	Pozitiile reprezentantilor sunt marcate cu R. Locul de intalnire care este marcat cu L R 0 1 0 0 0 1 0 0 0 0 1 R 0 0 L 0 0 0 0 R 0 0 0 0
4 4 2 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 3 2	5 0 0	Locurile posibile de intalnire sunt marcate cu L. Ele se suprapun cu locurile de start ale celor 2 reprezentanti. Solutia cea mai mica lexicografica este 0 0. L 0 1 0 L 1 0 0 L 1 0 0 L L L 0

Alex Palcuie Robert Hasna Andrei Vacaroiu

Universitatea din Bucuresti