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<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 9

struct Info{
	Info(int arg_code,int arg_sum_cost){
		code = arg_code;
		sum_cost = arg_sum_cost;
	}
	bool operator<(const struct Info &arg) const{ //総コストの昇順(PQ)
		return sum_cost > arg.sum_cost;
	}
	int code,sum_cost;
};

int N;
int table_index;
int table[40320][8],min_cost[40320];
int work[NUM],change_cost[NUM][NUM];
bool check[NUM];
map<int,int> MAP;

//N!の順列を作る
void makeCode(int index){

	if(index == N){

		int tmp = 0;

		for(int i = 0; i < N; i++){
			tmp = 10*tmp+work[i];
			table[table_index][i] = work[i];
		}

		MAP[tmp] = table_index;
		table_index++;

		return;
	}

	for(int i = 1; i <= N; i++){

		if(check[i])continue;
		check[i] = true;
		work[index] = i;
		makeCode(index+1);
		check[i] = false;
	}
}

int main(){

	scanf("%d",&N);

	for(int i = 1; i <= N; i++){
		for(int k = 1; k <= N; k++){
			scanf("%d",&change_cost[i][k]);
		}
	}

	//順列テーブルを作成する
	table_index = 0;
	for(int i = 1; i <= N; i++)check[i] = false;

	for(int i = 1; i <= N; i++){
		check[i] = true;
		work[0] = i;
		makeCode(1);
		check[i] = false;
	}

	//整列された状態を作る
	int first = 0,first_code;

	for(int i = 1; i <= N; i++){

		first = 10*first+i;
	}
	first_code = MAP[first];

	priority_queue<Info> Q;

	for(int i = 0; i < table_index; i++)min_cost[i] = BIG_NUM;

	min_cost[first_code] = 0;
	Q.push(Info(first_code,0));

	int next_num,next_code,next_cost;

	//整列された状態からの最短コストを求める
	while(!Q.empty()){

		if(Q.top().sum_cost > min_cost[Q.top().code]){
			Q.pop();
		}else{

			for(int i = 0; i < N; i++){

				work[i] = table[Q.top().code][i];
			}

			for(int i = 0; i < N-1; i++){ //交換する左側
				for(int k = i+1; k < N; k++){ //右

					next_cost = Q.top().sum_cost+change_cost[work[i]][work[k]];
					swap(work[i],work[k]);
					next_num = 0;
					for(int a = 0; a < N; a++){
						next_num = 10*next_num+work[a];
					}
					next_code = MAP[next_num];
					swap(work[i],work[k]); //元に戻す

					if(min_cost[next_code] > next_cost){

						min_cost[next_code] = next_cost;
						Q.push(Info(next_code,next_cost));
					}
				}
			}
			Q.pop();
		}
	}

	int ans = 0;
	for(int i = 0; i < table_index; i++){
		ans = max(ans,min_cost[i]);
	}

	printf("%d\n",ans);

	return 0;
}

