După ce în problema #Plata şi-a cumpărat biscuiţi, iar în problema #Maraton şi-a făcut temele, Costy s-a hotărât să meargă în vizită la prietenul său Paul. Și pentru că Paul este prietenul său cel mai bun, bineînţeles că nu se va duce cu mâna goala. Va trece pe la magazin şi îi va cumpăra un pachet de biscuiţi. Marea problemă a eroului nostru este oraşul rău famat, la fiecare intersecţie existând pericole. Oraşul are forma de două triunghiuri dreptunghice isoscele cu un vârf comun, ca în figura următoare:

C 
X X
X X X
X X X B
      X X
      X X X
      X X X P 

C – reprezintă poziţia iniţială a lui Costy, care se va afla mereu în colţul din stânga sus.

Exemplu

vizita.in

3
2 
-1 4
3 2 0
10 -3
3 1 2

vizita.out

16

Explicație

2 
-1 4
 3 2 0
     10 -3
      3 1 2

Se alege drumul format din 2, -1, 3, 2, 0, 10, -3, 1, 2.

#include <bits/stdc++.h>
using namespace std;

ifstream cin("vizita.in");
ofstream cout("vizita.out");

long long n , a[1002] , b[1002];

int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 1 ; j <= i ; j++)
        {
            cin >> a[j];
            if(j == 1) a[j] += b[j];
            else if(j == i) a[j] += a[j - 1];
            else  a[j] += min(b[j] , a[j - 1]);
        }
        for(int j = 1 ; j <= i ; j++)
            b[j] = a[j];
    }
    b[1] = a[n];
    for(int i = 2 ; i <= n ; i++)
    {
        for(int j = 1 ; j <= i ; j++)
        {
            cin >> a[j];
            if(j == 1) a[j] += b[j];
            else if(j == i) a[j] += a[j - 1];
            else  a[j] += min(b[j] , a[j - 1]);
        }
        for(int j = 1 ; j <= i ; j++)
            b[j] = a[j];
    }
    cout << a[n];
    return 0;
}