Problem statement

There is a permutation with $ 1,2, ..., N $ sorted. I want to select two different numbers $ i $, $ j $ and replace them repeatedly to make them sorted (in the order of $ 1,2, ..., N $). Every time you replace the numbers $ i $, $ j $, you need $ c_ {i, j} $.

Let $ f (p) $ be the minimum cost required to sort $ p $ for the permutation $ p $. Find the maximum possible value of $ f (p) $.

Constraint

* $ 2 \ leq N \ leq 8 $
* $ 0 \ leq c_ {i, j} \ leq 10 ^ 5 $
* $ c_ {i, j} = c_ {j, i} $
* $ c_ {i, i} = 0 $



input

Input follows the following format. All given numbers are integers.


$ N $
$ c_ {1,1} $ $ c_ {1,2} $ $ ... $ $ c_ {1, N} $
$ c_ {2,1} $ $ c_ {2,2} $ $ ... $ $ c_ {2, N} $
$ ... $
$ c_ {N, 1} $ $ c_ {N, 2} $ $ ... $ $ c_ {N, N} $

output

Output the maximum value on one line.

Example

Input

3
0 1 3
1 0 8
3 8 0


Output

5
#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;
}