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 <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

#define dump(a) (cerr << (#a) << " = " << (a) << endl)
#define FOR(it,c) for(__typeof((c).begin())it=(c).begin(); it!=(c).end();++it)
#define RFOR(it,c) for(__typeof((c).rbegin())it=(c).rbegin(); it!=(c).rend();++it)
#define exist(c, v) (find((c).begin(), (c).end(), (v)) != (c).end())

template<class T> inline void chmax(T& a, const T& b) { if(b > a) a = b; }
template<class T> inline void chmin(T& a, const T& b) { if(b < a) a = b; }

template<typename T, typename U> ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os << '(' << p.first << ", " << p.second << ')';
	return os;
}

template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
	copy(v.begin(), v.end(), ostream_iterator<T>(os, " "));
	return os;
}

typedef pair<int, string> P;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n;
	cin >> n;

	vector<vector<int> > c(n, vector<int>(n));
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < n; ++j)
			cin >> c[i][j];

	const string start = string("12345678").substr(0, n);

	map<string, int> cost;
	priority_queue<P, vector<P>, greater<P> > que;
	que.push(P(0, start));
	cost[start] = 0;

	while(!que.empty()) {
		const int c_cost = que.top().first;
		const string state = que.top().second;
		que.pop();

		if(cost[state] < c_cost)
			continue;

		for(int i = 0; i < n; ++i) {
			for(int j = i + 1; j < n; ++j) {
				string next = state;
				swap(next[i], next[j]);
				const int n_cost = c_cost + c[i][j];
				if(!cost.count(next) || cost[next] > n_cost) {
					cost[next] = n_cost;
					que.push(P(n_cost, next));
				}
			}
		}
	}

	int ans = 0;
	FOR(it, cost) {
		chmax(ans, it->second);
	}

	cout << ans << endl;
	

	return EXIT_SUCCESS;
}