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

Poveste si cerinta...

Praslea cel Voinic a gasit gradina cu meri cu mere de aur, dar are acum probleme cu paza acestora. A stat treaz ani la rand pana cand a decis sa construiasca un gard in jurul lor, astfel incat sa poata dormi linistit. Gradina are forma unui patrat cu latura $N$ metri. Praslea a impartit gradina in $N*N$ patrate de $1 m^2^$, patrate aranjate pe $N$ linii (numerotate de la $1$ la $N$) si $N$ coloane (numerotate de la $1$ la $N$). Fiecare mar se afla in unul dintre aceste patrate. Pentru a construi gardul, Praslea a decis sa selecteze un sir de patrate in care primul si ultimul patrat, precum si oricare 2 patrate consecutive in sir au cel putin un punct comun. Un patrat poate fi ales în sir o data sau de mai multe ori. In fiecare patrat din sir Praslea va plasa un stalp urias. Gardul format din acesti stalpi imparte gradina in doua zone (interior si exterior). Toti merii trebuie sa se afle in interior. Un patrat este considerat in interior daca nu exista drum de la un patrat situat pe marginea gradinii (linia $1$, coloana $1$, linia $N$ sau coloana $N$) la patratul respectiv. Un drum este un sir de patrate, astfel incat oricare doua patrate consecutive pe drum au o latura comuna, patratele de pe drum fiind libere (patrate care nu contin stalpi).
Plasarea unui stalp intr-un anumit patrat are un anumit cost. Daca un patrat apare de mai multe ori in sirul ales de Praslea atunci costul va fi adunat de tot atatea ori la costul total.
 
h2. Cerinta
 
Scrieti un program care sa determine costul total minim de construire a gardului respectand conditiile din enunt.

h2. Date de intrare

...

h2. Date de iesire