import std.stdio;
import std.c.stdio;
import std.range;
import std.array;
import std.functional;
import std.algorithm;
import std.conv;
import std.container;
import std.math;
import std.numeric;
import std.string;
import std.c.string;
import std.regex;
import std.typecons;

class Edge {
    string to;
    int cost;
    this(string to, int cost) {
        this.to = to;
        this.cost = cost;
    }
    override string toString() {
        return "Edge(" ~ to ~ ", " ~ cost.to!string ~ ")";
    }
}

string swapchar(in string s, int x, int y) {
    char[] ret = cast(char[])s.dup;
    swap(ret[x], ret[y]);
    return cast(string)ret;
}

void main() {
    int N; scanf("%d\n", &N);
    int[][] C = new int[][](N, N);
    foreach (i; 0 .. N) {
        foreach (j; 0 .. N) {
            scanf("%d", &C[i][j]);
        }
    }
    const X = "012345678";
    string x = X[0 .. N];
    Edge[][string] G;
    bool[string] used;
    void dfs(string v) {
        if (v in used) return;
        used[v] = true;
        foreach (i; 0 .. N) {
            foreach (j; i + 1 .. N) {
                string u = v.swapchar(i, j);
                if (u !in G) G[u] = [];
                G[v] ~= new Edge(u, C[i][j]);
                dfs(u);
            }
        }
    }
    dfs(x);

    struct S {
        string v;
        int cost;
    }
    BinaryHeap!(Array!S, "a.cost > b.cost") PQ;
    int[string] D; D[x] = 0;
    PQ.insert(S(x, 0));
    while (!PQ.empty) {
        S s = PQ.front; PQ.removeFront;
        foreach (edge; G[s.v]) {
            if (edge.to in D && s.cost + edge.cost >= D[edge.to]) continue;
            D[edge.to] = s.cost + edge.cost;
            PQ.insert(S(edge.to, D[edge.to]));
        }
    }
    writeln(D.reduce!max);
}