h2. Date de intrare

Pe prima linie a fisierului de intrare $gard4.in$ este scris numarul natural $N$ reprezentand dimensiunea gradinii. Urmatoarele $N$ linii contin cate $N$ numere separate prin cate un spatiu. Daca al $j$-lea numar de pe linia $i$ a fisierului este $-1$ atunci patratul din gradina situat pe linia $i-1$ si coloana $j$ contine un mar; altfel acel numar reprezinta costul de plasare a unui stalp in patratul de pe linia $i-1$ si coloana $j$.

h2. Date de iesire

FiÅŸierul de ieÅŸire $gard4.out$ va contine o singura linie pe care va fi scris un numar natural reprezentand costul minim total de plasare a stalpilor.

...

h2. Restrictii

* $3 ≤ N ≤ 35$
* $1 ≤ numarul de meri ≤ 5$
* costul plasarii unui stalp este un numar natural mai mare sau egal cu $0$ si mai mic decat $6666$
* nu vor exista meri pe marginea gradinii (linia $1$, coloana $1$, linia $N$ sau coloana $N$)
* evident, nu se poate plasa un stalp intr-un patrat ce contine un mar

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

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

| 5
  3  0 10 10 10
  10  1 10  0 10
  0 -1  4 -1  0
  10  0 10  0  0
  10 10 10 10  0
| 9

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

|
h3. Explicatie

...

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