shortestPath

import java.util.*;

public class MapRoute {
    private static class Graph {
        private ArrayList<Vertex> vertices;
        private int first;

        public Graph(int[][] map, int n) {
            this.vertices = new ArrayList<>();
            this.first = map[0][0];

            for (int i = 0; i < n * n; i++)
                this.vertices.add(new Vertex());

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (j < n - 1){
                        this.vertices.get(i + i * (n - 1) + j).to.add(vertices.get(i + i * (n - 1) + j + 1));
                        this.vertices.get(i + i * (n - 1) + j).weights.add(map[i][j + 1]);
                    }
                    if (i < n - 1){
                        this.vertices.get(i + i * (n - 1) + j).to.add(vertices.get(i + i * (n - 1) + j + n));
                        this.vertices.get(i + i * (n - 1) + j).weights.add(map[i + 1][j]);
                    }
                    if (j > 0 && i > 0 && i < n - 1){
                        this.vertices.get(i + i * (n - 1) + j).to.add(vertices.get(i + i * (n - 1) + j - 1));
                        this.vertices.get(i + i * (n - 1) + j).weights.add(map[i][j - 1]);
                    }
                    if (i > 0 && j > 0 && j < n - 1){
                        this.vertices.get(i + i * (n - 1) + j).to.add(vertices.get(i + i * (n - 1) + j - n));
                        this.vertices.get(i + i * (n - 1) + j).weights.add(map[i - 1][j]);
                    }
                }
            }
        }
    }

    private static class Vertex {
        private Vertex parent;
        private double dist;
        private ArrayList<Vertex> to;
        private ArrayList<Integer> weights;

        public Vertex() {
            this.parent = null;
            this.dist = Double.POSITIVE_INFINITY;
            this.to = new ArrayList<>();
            this.weights = new ArrayList<>();
        }
    }

    private static Comparator<Vertex> distComparator = new Comparator<Vertex>() {
        @Override
        public int compare(Vertex o1, Vertex o2) {
            return (int) (o1.dist - o2.dist);
        }
    };

    private static boolean relax(Vertex u, Vertex v, int w) {
        boolean changed = (u.dist + w) < v.dist;

        if (changed) {
            v.dist = u.dist + w;
            v.parent = u;
        }

        return changed;
    }

    private static void dijkstra(ArrayList<Vertex> graph, Vertex s) {
        PriorityQueue<Vertex> q = new PriorityQueue<>(distComparator);

        s.dist = 0;
        q.add(graph.get(0));

        while(!q.isEmpty()) {
            Vertex v = q.poll();

//          for (Vertex u: v.to) {
            for (int i = 0; i < v.to.size(); i++){
                Vertex u = v.to.get(i);
                if (relax(v, u, v.weights.get(i))) {
                    q.remove(u);
                    q.add(u);
                }
            }
        }
    }

    private static Graph scanGraph() {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int[][] map = new int[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                map[i][j] = in.nextInt();

        Graph graph = new Graph(map, n);
        return graph;
    }

    public static void main(String[] args) {
        //long start = System.currentTimeMillis();

        Graph graph = scanGraph();

        int n = graph.vertices.size();

        dijkstra(graph.vertices, graph.vertices.get(0));

        System.out.println(((int) graph.vertices.get(n - 1).dist + graph.first));

        //long end = System.currentTimeMillis();

        //System.out.println((end - start)/1000);
    }
}