triunghi

Se consideră o placă de dimensiune $n$, de forma unui triunghi echilateral, ale cărui laturi sunt denumite $A$, $B$ şi $C$ şi au lungimea egală cu $n$. Pe laturile $A$ şi $B$ sunt marcate câte $n-1$ puncte care împart laturile în $n$ porţiuni egale. Din fiecare punct marcat de pe latura $A$ se trasează un segment paralel cu latura $B$, iar din fiecare punct marcat de pe latura $B$ se trasează un segment paralel cu latura $A$. Celălalt capăt al fiecărui segment trasat se află pe latura $C$. În felul acesta, placa triunghiulară conţine $\frac{n \cdot (n + 1)}{2}$ plăci elementare (care nu sunt traversate de niciun segment). Astfel, pe o placă triunghiulară de dimensiune $n=4$, ca în figură, avem $6$ plăci elementare în formă de romb şi $4$ în formă de triunghi (cele cu o latură pe latura $C$ a plăcii triunghiulare).

Se doreşte împărţirea triunghiului în plăci elementare cu cost total minim. Dacă $n=1$ costul împărţirii este $0$. Pentru $n \geq 2$ singura operaţie permisă este tăierea de la un capăt la altul de-a lungul unui segment de lungime maximă, obţinându-se un triunghi de dimensiune $n-1$ şi o bandă. Banda va fi împărţită în plăci elementare prin tăieri de-a lungul segmentelor de lungime $1$ ce separă plăcile elementare care o compun. Triunghiul obţinut va fi împărţit mai departe în plăci elementare folosind în mod repetat operaţia descrisă mai sus. Costul total al împărţirii triunghiului de dimensiune $n$ în plăci elementare este egal cu costul tăierii de-a lungul segmentului de lungime maximă, plus costurile împărţirii benzii şi triunghiului de dimensiune $n-1$ obţinute, în plăci elementare.

Pe fiecare placă elementară este scris un număr. Costul unei tăieturi (fie că are loc într-un triunghi sau într-o bandă) este egal cu suma valorilor din plăcile elementare care au o latură comună cu segmentul pe care se face tăietura, înmulţită cu lungimea segmentului. Pentru un triunghi de dimensiune $n \geq 2$ există exact $2$ posibilităţi de a efectua o operaţie (corespunzătoare celor $2$ segmente de lungime maximă, unul paralel cu latura $A$, iar celălalt paralel cu latura $B$).

O tăiere pe direcţia $NV-SE$ (paralelă cu latura $B$) în triunghiul din figură are costul $(8+10+3+6+6+12) \cdot 3 = 135$. Costul împărţirii în plăci elementare a benzii obţinute este egal cu $(10+6) \cdot 1+(6+12) \cdot 1 + (12+5) \cdot 1 = 51$.

Cerinţă

Să se determine costul total minim necesar împărţirii plăcii triunghiulare în plăci elementare.

Date de intrare

În fişierul triunghi.in pe prima linie se află un număr natural nenul $n$, reprezentând dimensiunea plăcii. Pe a doua linie apar separate prin câte un spaţiu $\frac{n \cdot (n + 1)}{2}$ numere naturale, reprezentând valorile plăcilor elementare în ordinea parcurgerii de sus în jos şi apoi de la stânga la dreapta, conform figurii de mai sus.

Date de ieşire

În fişierul triunghi.out se va scrie pe prima linie costul total minim cerut.

Restricţii şi precizări

• $1 \leq n \leq 1 \ 000$
• $0 \leq$ numărul de pe o placă elementară $\leq 2 \ 000 \ 000 \ 000$
• Se garantează că rezultatul se va încadra pe $32$ biţi.
• Pentru $50\%$ din teste vom avea $n \leq 400$.

Exemplu

triunghi.in

4
10 8 6 4 3 12 3 1 6 5

triunghi.out

235

Explicație

Pentru a asigura costul total minim se poate realiza o tăietură pe direcţia $NE-SV$ de cost $3\cdot(10+6+8+3+4+1)=96$ la care se adaugă costul tăierii benzii în plăci elementare $3+4+4+8+8+10=37$. Placa triunghiulară rămasă va fi tăiată pe direcţia $NE-SV$. Costul tăieturii este $2\cdot(3+6+6+12)=54$, tăierea benzii în plăci elementare are costul $1+3+3+6=13$. Placa triunghiulară rămasă poate fi tăiată pe direcţia $NV-SE$. Costul tăieturii este $6+12=18$, tăierea benzii în plăci elementare are costul $12+5=17$, costul total minim este $235$.