Oracol

Gustavo, după ce a realizat că posedă abilitatea de a vedea în viitor, a decis că a venit momentul să treacă la următorul nivel și să-și valorifice capacitățile extrasenzoriale. Pentru a câștiga prestigiu și a deveni mai cunoscut în rândurile magicienilor profesioniști, acesta a ales să debuteze la Olimpiada Națională de Informatică prin prezicerea datelor de intrare pentru anumite probleme propuse în concurs. Primul client al lui Gustavo, Alfredo, ar dori să afle într-un mod inedit conținutul unui fișier de intrare aferent unei probleme de concurs, în care sunt scrise elementele unui șir $p$ de $N$ numere întregi. Pentru a face lucrurile mai interesante, Gustavo îi percepe o taxă de $C(i,j)$ bănuți pentru a-i divulga suma numerelor din șirul $p$ cu indici în intervalul $[i, j]$, anume $p_{i} + p_{i+1} + … + p_{j}$.

Cerință

Dându-se valoarea lui $N$ și toate valorile $C(i,j)$ cu $1 \leq i \leq j \leq N$, determinați costul total minim pe care trebuie să-l plătească Alfredo pentru a afla toate elementele șirului $p$.

Date de intrare

În fișierul oracol.in se află pe prima linie numărul natural $N$. Pe următoarele $N$ linii se află taxele percepute de Gustavo astfel: pe linia $i+1$ se vor afla $N-i+1$ numere naturale separate prin câte un spațiu, reprezentând în ordine costurile $C(i,i), C(i,i+1), …, C(i,N)$.

Date de ieșire

Fișierul de ieșire oracol.out va conține pe prima linie un singur număr care reprezintă costul total minim pe care trebuie să-l plătească Alfredo pentru a afla șirul $p$.

Restricții și precizări

• $1 \leq N \leq 1000$;
• pentru orice $1 \leq i \leq j \leq N$ se garantează $0 \leq C(i,j) \leq 1.000.000$;
• pentru teste în valoare de 48 puncte $1 \leq N \leq 250$.

Exemple

oracol.in

3
4 5 1
6 3
2

oracol.out

6

Explicație

Costul total minim este 6 și se obține astfel:
Cu un cost de valoare $C(1,3) = 1$ putem afla suma $p_1 + p_2 + p_3$.
Cu un cost de valoare $C(3,3) = 2$ putem afla valoarea lui $p_3$.
Cu un cost de valoare $C(2,3) = 3$ putem afla suma $p_2 + p_3$.
Din acestea putem afla exact toate elementele șirului $p$.