//#include <iostream>
#include <fstream>
#include <algorithm>
#include <cassert>

using namespace std;
int n;
const int N_MAX=20;
int c[N_MAX][N_MAX];
int c_sol[N_MAX][N_MAX];
int val;

/*void stampa(int k){
    cout<<"\n";
    if(k==0){
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++){
            cout<<c[i][j];
            if(j==n-1) cout<<"\n";            
        }
    }
    else
        for(int i=0; i<n-1; i++)
        for(int j=1; j<n; j++){
            cout<<c_sol[i][j];
            if(j==n-1) cout<<"\n";            
        }
        
}*/
 /*
void path_cost{
        //trova il massimo di una colonna
        for(int i=0;i<n;i++)
            for(int j=1;j<n;j++)
                

}
 */
/* Mantengo una tabella c_sol, nella quale ogni colonna è un nodo
 dal 2 a n. Data una riga (un nodo) ciascuna cella rappresenta il costo per raggiungere il nodo colonna
    avendo considerato gli archi dei nodi sino al nodo riga. In pratica arricchiamo il grafo di
    archi dei nodi di riga e man mano aggiorniamo il costo per arrivare al nodo che ci interessa nel nodo colonna.
    Ho trovato alla fine del procedimento il costo massimo per ciascun nodo. Non resta che costruire il cammino semplice da 1 a n.

*/
void visita(){

//inizializzo la prima riga di c_sol che corrisponde ai costi degli archi uscenti dal nodo 1.
    for(int i=1; i<n;i++)
        c_sol[0][i]=c[0][i];
    
    for(int i=1; i<n-1; i++)
        for(int j=1; j<n; j++){
            if(i!=j){
                //non i-1, ma un nodo che non passi da da i-1
                if(c[i][j]+c_sol[0][i] > c_sol[i-1][j]){
                    c_sol[i][j]=c[i][j]+c_sol[0][i];               
                }
                else c_sol[i][j]= c_sol[i-1][j];
            
            } else c_sol[i][j]= c_sol[i-1][j];                     
        }
// stampa(2);
}

//prendo il massimo della tabella generata, e mando l'ultimo arco in n. SE ho piu massimi???introduco max1.
//a parita di massimo, prendo quello con l-arco uscente in n con peso maggiore.
int sol(){
    int max=0;
    int k=0;
    int max1=0;
    for(int i=1; i<n-1; i++)
        for(int j=1; j<n; j++){
            if(c_sol[i][j]>max && c[j][n-1]>=max1){
                max=c_sol[i][j];
                k=j;
                }
        }
   // cout<<k<<" "<<max<<endl;
    int max_cost=max+c[k][n-1];
return max_cost;
}

int main(){
    ifstream fin("input.txt"); assert(fin);
    fin >> n;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            fin >> c[i][j];
   //stampa(0);
    visita();
    ofstream fout("output.txt"); assert(fout);
    fout << sol();
}