import java.util.*;

public class MapRoute {
    public static void main(String[] arguments) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int[] is=new int[n*n], d=new int[n*n];
        PQ pq=new PQ(n);
        V v;
        for (int i=0; i < n*n; i+=1) {
            is[i]=in.nextInt();d[i]=Integer.MAX_VALUE;
        }
        d[0]=is[0];
        for (int i=0; i < n*n; i+=1) pq.ins(new V(i, d[i]));
        while (pq.l!=0) {
            v= pq.ext();
            if (v.i>n-1 && d[v.i-n]>d[v.i]+is[v.i-n]) {
                d[v.i-n]=d[v.i]+is[v.i-n];pq.rm(new V(v.i-n, d[v.i-n]));
            }
            if (v.i<n*n-n && d[v.i+n]>d[v.i]+is[v.i+n]) {
                d[v.i+n]=d[v.i]+is[v.i+n];pq.rm(new V(v.i+n, d[v.i+n]));
            }
            if (v.i%n!=0 && d[v.i-1]>d[v.i]+is[v.i-1]) {
                d[v.i-1]=d[v.i]+is[v.i-1];pq.rm(new V(v.i-1, d[v.i-1]));
            }
            if (v.i%n!=n-1 && d[v.i+1]>d[v.i]+is[v.i+1]) {
                d[v.i+1]= d[v.i]+is[v.i+1];pq.rm(new V(v.i+1, d[v.i+1]));
            }
        }
        System.out.println(d[n*n-1]);
    }
}

class V {
    public int d, i;
    V(int i, int d) {this.i=i; this.d=d;}
    public boolean cmp(V v) {return d-v.d>0;}
}

class PQ {
    public int l;
    public V[] vs;
    public int[] h;
    public PQ(int n) {
        l = 0;vs = new V[n*n+2*n+1]; h = new int[n*n+2*n+1];
    }
    public void ins(V x) {
        l++;
        while (l>1 && vs[l>>1].cmp(x)) {
            vs[l]=vs[l>>1];h[vs[l].i] = l;l=l>>1;
        }
        vs[l] = x;h[vs[l].i] = l;
    }
    public void rm(V x) {
        while (h[x.i]-1>0 && vs[h[x.i]>>1].cmp(x)) {
            vs[h[x.i]]=vs[h[x.i]>>1];h[vs[h[x.i]].i] = h[x.i];h[x.i]=h[x.i]>>1;
        }
        vs[h[x.i]] = x;h[vs[h[x.i]].i] = h[x.i];
    }
    public V ext() {
        V x = vs[1];l--;int i = 1, c;
        if (2>l)c = 0;
        else if (2==l || vs[3].cmp(vs[2]))c = 2;
        else c = 3;
        while(c > 0 && vs[l + 1].cmp(vs[c])) {
            vs[i] = vs[c];h[vs[i].i] = i;i = c;
            if ((i<<1)-l>0)c = 0;
            else if ((i<<1)-l==0 || vs[(i<<1)+1].cmp(vs[i<<1]))c = i<<1;
            else c=(i<<1)+1;
        }
        vs[i] = vs[l+1];h[vs[i].i] = i;return x;
    }
}