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

const int INF = 1e+9;
const int MAX_V = 40320;
struct edge{ int to, cost; };
typedef pair<int,int> P;

int n;
int c[10][10];
map<vector<int>,int> m;
int fact[9] = {1,1,2,6,24,120,720,5040,40320};

int V;
vector<edge> G[MAX_V];
int d[MAX_V];

void dijkstra(int s){
	priority_queue<P,vector<P>,greater<P> > que;
	fill( d , d+V , INF );
	d[s] = 0;
	que.push( P(0,s) );
	
	while( !que.empty() ){
		P p = que.top(); que.pop();
		int v = p.second;
		if( d[v] < p.first ) continue;
		for(int i=0 ; i < G[v].size() ; i++ ){
			edge e = G[v][i];
			if( d[e.to] > d[v] + e.cost ){
				d[e.to] = d[v] + e.cost;
				que.push( P(d[e.to],e.to) );
			}
		}
	}
}

int main(){
	cin >> n;
	for(int i=0 ; i < n ; i++ ){
		for(int j=0 ; j < n ; j++ ){
			cin >> c[i][j];
		}
	}
	
	// m[hÍ n!
	V = fact[n];
	// {1, 2, ... , n}ÌñðÂ­é
	vector<int> p;
	for(int i=1 ; i <= n ; i++ ){
		p.push_back( i );
	}
	// CÓÌñ p É 0 ©ç (n!-1)ÌÔðUé
	int k = 0;
	do{
		m[p] = k;
		k++;
	}while( next_permutation(p.begin(),p.end()) );
	
	// CÓÌñ p ÉÂ¢ÄCÓÌi,j(0 <= i < j < n )ðð··éRXgc[i][j]ÅGbWÌRXgð£é
	do{
		for(int i=0 ; i < n ; i++ ){
			for(int j=i+1 ; j < n ; j++ ){
				int u = m[p];
				swap( p[i] , p[j] );
				int v = m[p];
				swap( p[i] , p[j] );
				
				edge e;
				e.to = v;
				e.cost = c[i][j];
				G[u].push_back( e );
				e.to = u;
				G[v].push_back( e );
			}
		}
	}while( next_permutation(p.begin(),p.end()) );
	
	// m[h0 ({1, 2, ... , n}) ©çÌÅZoH(f(p)É)ðßé
	dijkstra( 0 );
	// f(p)ÌÅålðßé
	int ans = 0;
	for(int i=1 ; i < V ; i++ ){
		ans = max( ans , d[i] );
	}
	cout << ans << endl;
}