#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int maximo(int a, int b) {
   if (a >= b) return a; else return b;
}

int maxdist(int destino, vector< vector<int> > & tarifas, vector<int> & costes) {
   int max = INT_MIN;
   for (int i = 0; i < destino; ++i) {
         if (i == 0) {
             if (max < tarifas[i][destino]) max = tarifas[i][destino];
         }
         else {
             if (costes[i] == INT_MIN) {
                costes[i] = maxdist(i,tarifas,costes);
                int x = maximo(tarifas[i][destino] , costes[i] + tarifas[i][destino]);
                if (x > max) max = x;
             }
             else {
                int x = maximo(tarifas[i][destino] , costes[i] + tarifas[i][destino]);
                if (x > max) max = x;
             }
         }
   }
   return max;

}

int main() {
    int n;
    cin >> n;
    if (n == 1) {
     int result;
     cin >> result;
     cout << result << endl;
    }
    else {
        vector< vector<int> > tarifas(n,vector<int> (n));
        vector<int> costes(n,INT_MIN);
        int max = INT_MIN;
        for (int i = 0; i < n; ++i) {
           for (int j = 0; j < n; ++j) {
                  cin >> tarifas[i][j];
           }
        }

        for (int i = 1; i < n; ++i) {
           int x = maxdist(i,tarifas,costes);
           if (x > max) max = x;
        }
        cout << max << endl;
    }

}