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

%{float: right;}!problema/livada2?por_costel_balada.jpg!%
 

Por Costel a descoperit o scriere din mitologia porceasca: “Balada Porcului”. Balada descrie o poveste de dragoste dintre un porc si o purcica. Intr-unul din capitole, porcul vrea sa-si impresioneze aleasa prin ridicarea unui cotet. Nu reuseste, insa, limitat fiind de eterna sa conditie de porc. Dar acesta spune apoi ca:

                        _             Am gasit, insa, la urma,_
 			_              O livada cat o ferma,_
                        _              Ascunsa-n inima padurii,_
 			_              Strapunsa de lumina lunii,_
                        _              Si o tufa drept cotet_
                        _              Pentru porcul iubaret._

                        _Am gasit, insa, la urma,_
 			_O livada cat o ferma,_
                        _Ascunsa-n inima padurii,_
 			_Strapunsa de lumina lunii,_
                        _Si o tufa drept cotet_
                        _Pentru porcul iubaret._

Por Costel nu este impresionat, insa, nici de rimele fortate, nici de figurile de stil exagerate. “O padure e plina de livezi” zice el, “se pune problema doar cum o alegi”.

Se da o matrice de <tex>N</tex> linii si <tex>M</tex> coloane ce descrie o “padure”. Fiecare celula are o valoare intreaga (pozitiva sau negativa) - gradul de frumusete al acelei celule. Se cere alegerea unei “livezi” adica o submultime de celule care satisface criteriile:
 
* Este nevida

Se da o matrice de N linii si M coloane ce descrie o “padure”. Fiecare celula are o valoare intreaga (pozitiva sau negativa) - gradul de frumusete al acelei celule. Se cere alegerea unei “livezi” adica o submultime nevida de celule care satisface criteriile:

* Este “conexa” (adica se poate ajunge dintr-o celula in oricare alta trecand numai prin celule care au o latura comuna)

* Intersectia submultimii cu o linie a matricei este fie multimea vida, fie o secventa “conexa” (aceeasi definitie ca mai sus) de celule. Cu alte cuvinte, pe fiecare linie, submultimea are fie nicio celula, fie un interval continuu de celule.

* Intersectia submultimii cu o linie a matricei este fie multimea vida, fie o secventa “conexa” (aceeasi definitie ca mai sus) de celule

Dintre toate submultimile de celule cu aceasta proprietate, va cerem sa o alegeti pe cea cu suma gradelor de frumusete maxima.

Dintre toate submultimile de celule cu aceasta proprietate, va cereme sa o alegeti pe cea cu suma gradelor de frumusete maxima.

h2. Date de intrare
Fişierul de intrare $livada2.in$ va contine pe prima linie <tex>T</tex>, numarul de teste.

Fiecare din cele <tex>T</tex> teste are formatul urmator: pe prima linie, cor fi doua numere naturale <tex>N</tex> si <tex>M</tex>, numarul de linii si numarul de coloane al matricei. Pe urmatoarele <tex>N</tex> linii vor fi afisate cate M numere separate prin spatii. Al <tex>j</tex>-lea numar de pe a <tex>i</tex>-a linie semnifica gradul de frumusete al celulei <tex>(i,j)</tex>.

Fiecare din cele T teste are formatul urmator: pe prima linie, cor fi doua numere naturale <tex>N</tex> si <tex>M</tex>, numarul de linii si numarul de coloane al matricei. Pe urmatoarele N linii vor fi afisate cate M numere separate prin spatii. Al j-lea numar de pe a i-a linie semnifica gradul de frumusete al celulei (i,j).

h2. Date de ieşire

h2. Restricţii

* <tex>T</tex> &le; <tex>5</tex>
* <tex>1</tex> &le; <tex>M</tex>,<tex>N</tex> &le; <tex>300</tex>
* <tex>-10^4</tex> &le; gradul de frumusete al unei celule &le; <tex>10^4</tex>

* 1 &le; <tex>M</tex>,<tex>N</tex> &le; 300$
* -10^4 &le; gradul de frumusete al unei celule &le; 10^4

h2. Exemplu
table(example). |_. livada2.in |_. livada2.out |

| 1
  3 4
  5 -3 0 0
  -2 3 3 4
  -7 -6 4 -5
| 17

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

Livada contine celulele (1,1), (2,1), (2,2), (2,3), (2,4), (3,3)

...

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

10327