smax

H. Smax

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

Poveste şi cerinţă...

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$ ...

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$ ...

Î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

* $... ≤ ... ≤ ...$

* **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") ==