#include<map>
#include<queue>
#include<cstdio>
#include<algorithm>

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

using namespace std;

const int INF=1<<29;

int main(){
	int n; scanf("%d",&n);
	int cost[8][8];
	rep(i,n) rep(j,n) scanf("%d",cost[i]+j);

	int n_perm=0;
	map<vector<int>,int> f;
	vector<int> f_inv[40320];
	vector<int> perm(n);
	rep(i,n) perm[i]=i;
	do{
		f[perm]=n_perm;
		f_inv[n_perm]=perm;
		n_perm++;
	}while(next_permutation(perm.begin(),perm.end()));

	// Dijkstra
	int d[40320];
	rep(u,n_perm) d[u]=INF;
	d[0]=0;
	priority_queue< pair<int,int> > Q; Q.push(make_pair(0,0));
	while(!Q.empty()){
		int d_now=-Q.top().first,u=Q.top().second; Q.pop();
		if(d_now>d[u]) continue;

		vector<int> p=f_inv[u];
		rep(j,n) rep(i,j) {
			swap(p[i],p[j]);
			int v=f[p];
			if(d[u]+cost[i][j]<d[v]){
				d[v]=d[u]+cost[i][j];
				Q.push(make_pair(-d[v],v));
			}
			swap(p[i],p[j]);
		}
	}

	printf("%d\n",*max_element(d,d+n_perm));

	return 0;
}