Fişierul intrare/ieşire:	rland.in, rland.out	Sursă	preONI 2002
Autor	Mugurel Ionut Andreica	Adăugată de	Mugurel-Ionut Andreica •mugurelionut
Timp execuţie pe test	0.025 sec	Limită de memorie	5096 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Rland

Doi buni prieteni s-au decis sa isi cumpere terenuri intr-o zona a orasului in care locuiesc. Orasul este reprezentat printr-o matrice patratica de dimensiune N, iar fiecare patrat al matricii reprezinta o zona de dimensiune unitara a orasului. Pentru fiecare zona de dimensiune unitara a orasului se cunoaste valoarea ei, care este un numar intreg intre -150 si 150. Primul dintre cei doi prieteni vrea sa isi cumpere un teren de forma dreptunghiulara avand P linii si Q coloane, inclus complet in oras, care sa aiba valoarea maxima posibila. Valoarea terenului este reprezentata de suma valorilor zonelor de dimensiune unitara pe care le include (in numar de P*Q).

Cel de-al doilea prieten vrea sa isi cumpere si el un teren de forma dreptunghiulara, care sa aiba exact Q coloane (acelasi numar de coloane ca si terenul pe care vrea sa il cumpere prietenul sau) si maxim P linii (adica numarul de linii ale terenului poate fi 1,2,..,P). Bineinteles, si el doreste ca terenul sau sa fie complet inclus in oras si sa aiba o valoare maxima posibila. Valoarea terenului este data de suma valorilor zonelor de dimensiune unitara pe care le include (in numar de L*Q, 1 ≤ L ≤ P).

Date de intrare

Pe prima linie a fisierului rland.in se vor afla numerele N, P si Q (separate prin cate un spatiu). Pe urmatoarele N linii se vor afla cate N numere intregi (separate prin spatii), reprezentand valorile zonelor de dimensiune unitara care fac parte din oras.

Date de iesire

Pe prima linie a fisierului rland.out veti afisa numerele S i j , separate prin cate un spatiu. S va reprezenta valoarea maxima a terenului pe care vrea sa il cumpere primul prieten, iar i si j vor reprezenta linia, respectiv coloana din matricea orasului a coltului stanga-sus al acestui teren (terenul va contine toate zonele de dimensiune unitara avand numarul liniei intre i si i+P-1 si numarul coloanei intre j si j+Q-1). Daca exista mai multe terenuri cu aceeasi suma maxima, veti afisa coordonatele coltului stanga-sus numai a unuia dintre ele.

Pe a doua linie veti afisa numerele X L a b, separate prin cate un spatiu. X reprezinta valoarea maxima a terenului pe care vrea sa il cumpere cel de-al doilea prieten, L reprezinta numarul de linii al acestui teren ($1 ≤ L ≤ P$), iar a si b reprezinta linia, respectiv coloana coltului stanga-sus al acestui teren. Terenul va contine zonele unitare cu coordonatele liniei intre a si a+L-1, si coordonatele coloanei intre b si b+Q-1. Daca exista mai multe terenuri cu aceeasi suma maxima, veti afisa coordonatele coltului stanga-sus numai a unuia din ele.

Restrictii

• 4 ≤ N ≤ 150

Exemplu

table(example). |_. rland.in |_. rland.out |
| 4 2 3
-1 -1 -1 -1
-1 1 -1 -1
-1 -1 -1 4
-1 -1 -1 -1 |
1 2 2
2 1 3 2|

Cum se trimit solutii?