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 metri. Prâslea a împărţit grădina în pătrate de , pătrate aranjate pe linii (numerotate de la la ) şi coloane (numerotate de la la ). 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 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 , coloana , linia sau coloana ) 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 reprezentând dimensiunea grădinii. Următoarele linii conţin câte numere separate prin câte un spaţiu. Dacă al -lea număr de pe linia a fişierului este - atunci pătratul din grădină situat pe linia şi coloana conţine un măr; altfel acel număr reprezintă costul de plasare a unui stâlp în pătratul de pe linia şi coloana .
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 și precizări
- numărul de meri
- Costul plasării unui stâlp este un număr natural mai mare sau egal cu şi mai mic decât .
- Nu vor exista meri pe marginea grădinii (linia , coloana , linia sau coloana ).
- Evident, nu se poate plasa un stâlp într-un pătrat ce conţine un măr.
Exemplu
gard.in
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
gard.out
9
Explicație
Şirul de pătrate ales pentru plasarea stâlpilor este următorul:
După cum observaţi, pătratul de cost dintre cei doi meri a fost ales de ori.