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 <queue>
#include <map>
#include <cstring>
#include <algorithm>
#include <fstream>
#define rep(i,n) for(int i=0;i<(n);i++)
#define ALL(A) A.begin(), A.end()

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
struct edge{ int to, cost; };

const int INF = 1<<30;
const int MAX_V = 40500;
int N, V;
int d[MAX_V];
int cost[10][10];
vector<edge> G[MAX_V];

int factorial (int n )
{
	if (n == 0 ) return 1;

	return n*factorial (n-1 );
}

void make_edge (map<vector<int>, int> node )
{
	map<vector<int>, int>::iterator it = node.begin();
	for (; it != node.end(); it++ ){
		vector<int> s = (*it).first;
		int from = (*it).second;
		rep (i, N ){
			for (int j = i+1; j < N; j++ ){
				int c = cost[i][j];
				swap (s[i], s[j] );
				int to = node[s];
				edge e;
				e.to = to, e.cost = c;
				G[from].push_back (e );
				swap (s[i], s[j] );
			} // end for
		} // end rep
	} // end for
}

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;
		rep (i, G[v].size() ){
			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 ) );
			} // end if
		} // end rep
	} // end while
}

int main()
{
	memset (cost, 0, sizeof (cost ) );
	cin >> N;
	int n = N;

	V = factorial(n );

	rep (i, n ) rep (j, n ) cin >> cost[i][j];

	vector <int> order(n, 0 );
	map <vector<int> , int>  node;

	rep (i, n ) order[i] = i;

	int cnt = 0;
	do{
		node[order] = cnt;
		cnt++;
	} while (next_permutation (ALL (order ) ) );	

	make_edge (node );
	dijkstra (0 );

	int res = 0;
	rep (i, V )
		res = max (res, d[i] );

	cout << res << endl;
		
	return 0;
}