smax

H. Smax

== include(page="template/taskheader" task_id="smax") ==

Fie **A[][]** o matrice cu **N** linii şi **M** coloane ce conţine numere naturale. Care este suma maximă a două elemente de pe poziţii distincte din **A[][]** care au distanţă Manhattan dintre coordonatele lor mai mică sau egală cu **D**?

Fie **A[][]** o matrice cu **N** linii şi **M** coloane ce conţine numere naturale. Care este suma maximă a două elemente de pe poziţii distincte din **A[][]** care se află la distanţă Manhattan maxim **D**?

h2. Date de intrare

Fişierul de intrare $smax.in$ conţine pe prima linie **T**, numărul de teste. Fiecare test este descris în continuare. Pe prima linie se află trei numere: **N**, **M** şi **D** iar următoarele linii conţin câte **M** numere separate prin câte un spaţiu, elementele matricii în ordine.

Fişierul de intrare $smax.in$ conţine pe prima linie **T**, numărul de teste. Pentru fiecare test în continuare sunt scrise trei numere: **N**, **M** şi **D** pe prima linie iar următoarele **N** linii conţin câte **M** numere separate prin câte un spaţiu, elementele matricii în ordine.

h2. Date de ieşire

h2. Restricţii

* T = 5
* 2 ≤ **N**, **M**, **D** ≤ 1000
* 0 ≤ **A[i][j]** ≤ 1000 000 000
* Distanţa Manhattan dintre elementele de la poziţiile (i{~1~}, j{~1~}) şi (i{~2~}, j{~2~}) este suma diferenţelor în modul: abs(i{~1~}-i{~2~}) + abs(j{~1~}-j{~2~})

* **T** = 5
* 2 ≤ **N**, **M**, **D** ≤ 500
* 0 ≤ **A{~i,j~}** ≤ 1000 000 000
* Distanţa Manhattan dintre elementele de la poziţiile (i{~1~}, j{~1~}) şi (i{~2~}, j{~2~}) este |i{~1~}-i{~2~}| + |j{~1~}-j{~2~}|, unde |x| este modulul lui x.

h2. Exemplu