#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
using namespace std;

#define rep(i,n) for(int i=0; i<(int)n; ++i)

int n;
int cost[8][8];

inline int encode(const vector<int> &v) {
    int ret = 0;
    for(int i=0; i<v.size(); ++i)
        ret |= (v[i]<<(i*3));
    return ret;
}

inline int get(const int x,int idx) { return 7&(x>>(idx*3)); }

int solve() {
    map<int,int> dist;
    set<int> seen;
    vector<int> s(n);
    for(int i=0; i<n; ++i) s[i] = i;
    dist[encode(s)] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > q; q.push(make_pair(0,encode(s)));

    while(!q.empty()) {
        pair<int,int> p = q.top(); q.pop();
        int d = p.first,st = p.second;

        if(seen.find(st) != seen.end()) continue;
        seen.insert(st);

        for(int i=0; i<n; ++i) s[i] = get(st,i);
        // for(int i=0; i<n; ++i) cout<<s[i]<<" ";
        // cout<<endl;

        for(int i=0; i<n; ++i)
            for(int j=0; j<n; ++j) {
                swap(s[i],s[j]);
                int nd = d+cost[s[i]][s[j]];
                int ns = encode(s);
                if(dist.find(ns) == dist.end() || dist[ns] > nd) {
                    dist[ns] = nd;
                    q.push(make_pair(nd,ns));
                }
                swap(s[i],s[j]);
            }
    }

    int ans = 0;
    for(map<int,int>::iterator it = dist.begin(); it != dist.end(); ++it)
        ans = max(ans, it->second);

//    cout<<dist.size()<<endl;
    return ans;
}

int main() {
    cin>>n;
    rep(i,n) rep(j,n) cin>>cost[i][j];
    cout<<solve()<<endl;
}