Prâslea cel Voinic a găsit grădina cu meri cu mere de aur, dar are acum probleme cu paza acestora. A stat treaz ani la rând până când a decis să construiască un gard în jurul lor, astfel încât să poată dormi liniştit.
Grădina are forma unui pătrat cu latura N metri. Prâslea a împărţit grădina în N*N pătrate de 1 m², pătrate aranjate pe N linii (numerotate de la 1 la N) şi N coloane (numerotate de la 1 la N). Fiecare măr se află în unul dintre aceste pătrate.
Pentru a construi gardul, Prâslea a decis să selecteze un şir de pătrate în care primul şi ultimul pătrat, precum şi oricare 2 pătrate consecutive în şir au cel puţin un punct comun. Un pătrat poate fi ales în şir o dată sau de mai multe ori. În fiecare pătrat din şir Prâslea va plasa un stâlp uriaş. Gardul format din aceşti stâlpi împarte grădina în două zone (interior şi exterior). Toţi merii trebuie să se afle în interior. Un pătrat este considerat în interior dacă nu există drum de la un pătrat situat pe marginea grădinii (linia 1, coloana 1, linia N sau coloana N) la pătratul respectiv. Un drum este un şir de pătrate, astfel încât oricare două pătrate consecutive pe drum au o latură comună, pătratele de pe drum fiind libere (pătrate care nu conţin stâlpi).
Plasarea unui stâlp într-un anumit pătrat are un anumit cost. Dacă un pătrat apare de mai multe ori în şirul ales de Prâslea atunci costul va fi adunat de tot atâtea ori la costul total.

Cerinţă

Scrieţi un program care să determine costul total minim de construire a gardului respectând condiţiile din enunţ.

Date de intrare

Pe prima linie a fişierului de intrare gard.in este scris numărul natural N reprezentând dimensiunea grădinii. Următoarele N linii conţin câte N numere separate prin câte un spaţiu. Dacă al j-lea număr de pe linia i a fişierului este -1 atunci pătratul din grădină situat pe linia i-1 şi coloana j conţine un măr; altfel acel număr reprezintă costul de plasare a unui stâlp în pătratul de pe linia i-1 şi coloana j.

Date de ieşire

Fişierul de ieşire gard.out va conţine o singură linie pe care va fi scris un număr natural reprezentând costul minim total de plasare a stâlpilor.

Restricţii

2 < N < 36
0 < numărul de meri < 6
Costul plasării unui stâlp este un număr natural mai mare sau egal cu 0 şi mai mic decât 6666.
Nu vor exista meri pe marginea grădinii (linia 1, coloana 1, linia N sau coloana N).
Evident, nu se poate plasa un stâlp într-un pătrat ce conţine un măr.

Exemple

gard.in	gard.out	Explicaţii
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	Şirul de pătrate ales pentru plasarea stâlpilor este următorul: După cum observaţi, pătratul de cost 4 dintre cei doi meri a fost ales de două ori.

autor: Dan Ionut Fechete

propunător: Prof. Emanuela Cerchez

Liceul de Informatica ″Grigore Moisil″

emanuela.cerchez@gmail.com