Fişierul intrare/ieşire:	vladut.in, vladut.out	Sursă	ad-hoc
Autor	Ciprian Oprisa, Tudor Muresan	Adăugată de	Ciprian Oprisa •cypry
Timp execuţie pe test	0.25 sec	Limită de memorie	16384 kbytes
Scorul tău	N/A	Dificultate	N/A

Războiul lui Vlăduț

În Ţinutul de Mijloc, elfii şi orcii trăiesc în pace. Vlăduţ, regele orcilor, decide să tulbure pacea şi să atace ţinutul.

Cucerirea ţinutului e o treabă uşoară, dar nu e la fel de uşor să îl păstreze, deoarece elfii care trăiesc acolo nu vor fi tocmai prietenoşi. Din acest motiv, Vlăduţ doreşte să anexeze doar o regiune, sub formă de dreptunghi cu laturile paralele cu axele, astfel încât diferenţa dintre numărul de orci şi numărul de elfi care trăiesc în acea regiune să fie cât mai mare.

Ţinutul de Mijloc este reprezentat printr-un pătrat de latură $n$ , format din $n \times n$ zone. Pentru fiecare zonă se cunoaşte numărul de orci şi numărul de elfi care trăiesc acolo, date prin matricile $O$ şi $E$ . Pentru fiecare zonă aflată la coordonatele $i$ şi $j$ , cu $1 \leq i, j \leq n$ , $O[i][j]$ reprezintă numărul de orci din zona respecitvă, iar $E[i][j]$ reprezintă numărul de elfi din zona respectivă.

Ajutaţi-l pe Vlăduţ să afle ce regiune ar fi cel mai bine să anexeze, calculând diferenţa maximă dintre numărul de orci şi numărul de elfi pe care o poate obţine.

În imaginea de mai sus avem cele două hărţi ale Ţinutului de Mijloc, de dimensiune $4 \times 4$ . Decizia optimă pentru Vlăduţ e să anexeze regiunea dreptunghiulară cu colţul stânga-sus la coordonatele $(2, 1)$ şi colţul stânga-jos la coordonatele $(4, 2)$ . În această regiune trăiesc $47+118+65+65+73+27=395$ orci şi $38+116+69+64+74+19=380$ elfi, deci diferenţa obţinută este 15.

Date de intrare

Fişierul de intrare vladut.in conţine pe prima linie numărul de teste $T$ . Fiecare test începe cu o linie care conţine numărul $n$ , dimensiunea laturii Ţinutului de Mijloc. Următoarele $2 \cdot n$ linii conţin cele două matrici $O$ şi $E$ . Primele $n$ linii corespund matricii $O$ , iar următoarele $n$ linii corespund matricii $E$ . Pe fiecare linie se vor găsi $n$ numere întregi, separate prin spaţii.

Date de ieşire

În fişierul de ieşire vladut.out se va tipări pe fiecare linie numărul testului (primul test are numărul 1), urmat de caracterul ':' şi de diferenţa maximă dintre numărul de orci şi numărul de elfi pe care o poate obţine Vlăduţ.

Restricţii

$1 \leq T \leq 10$
$1 \leq n \leq 100$
$0 \leq O[i][j] \leq 127, \forall i, j \in \mathbb{N}, 1 \leq i, j \leq n$
$0 \leq E[i][j] \leq 127, \forall i, j \in \mathbb{N}, 1 \leq i, j \leq n$
există cel puţin o zonă în care numărul de orci este mai mare decât numărul de elfi

Exemplu

vladut.in	vladut.out
1 4 90 88 39 90 47 118 5 91 65 65 51 6 73 27 107 37 90 90 46 90 38 116 11 89 69 64 55 5 74 19 107 39	1:15

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

infoarena informatica de performanta

Războiul lui Vlăduț

Date de intrare

Date de ieşire

Restricţii

Exemplu