smax

H. Smax

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

Fie A[][] o matrice cu N linii si M coloane de numere naturale. Care este suma maxima a doua elemente de pe pozitii distincte din A[][] care au distanta Manhattan dintre coordonatele lor mai mica sau egala 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$ contine pe prima linie T, numarul de teste. Fiecare test este descris in continuare. Pe prima linie se afla cele trei numere: N, M si D iar urmatoarele linii contin cate M numere separate prin cate un spatiu, elementele matricii in 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

În fişierul de ieşire $smax.out$ afisati pe cate o linie separata raspunsul la fiecare test, suma maxima.

În fişierul de ieşire $smax.out$ afişaţi pe câte o linie separată răspunsul la fiecare test, suma maximă.

h2. Restricţii

* 2 ≤ N, M, D ≤ 1000
* 0 ≤ A[i][j] ≤ 1000 000 000

* **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

table(example). |_. smax.in |_. smax.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

table(example). |_. smax.in |_. smax.out |_. Explicaţie |
| 2
5 5 3
1 1 1 1 1
1 1 4 1 1
1 2 1 2 1
1 1 3 1 1
1 1 1 1 1
3 5 4
8 1 4 2 3
2 5 4 6 3
2 3 6 5 7
| 7
14
| 7 = 4 + 3
  14 = 8 + 6
|

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