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 <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>


using namespace std;

#ifdef _MSC_VER
#define __typeof__ decltype
template <class T> int __builtin_popcount(T n) { return n ? 1 + __builtin_popcount(n & (n - 1)) : 0; }
#endif

#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define CLEAR(arr, val) memset(arr, val, sizeof(arr))

#define rep(i, n) for (int i = 0; i < n; ++i)

template <class T> void max_swap(T& a, const T& b) { a = max(a, b); }
template <class T> void min_swap(T& a, const T& b) { a = min(a, b); }

typedef long long ll;
typedef pair<int, int> pint;

const double EPS = 1e-8;
const double PI = acos(-1.0);
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };
bool valid_pos(int x, int y, int w, int h) { return 0 <= x && x < w && 0 <= y && y < h; }


typedef unsigned int uint;
typedef pair<int, uint> iu;

uint encode(const vector<int>& v)
{
	uint res = 0;
	for (int i = (int)v.size() - 1; i >= 0; --i)
		res = (res << 4) + v[i];
	return res;
}
vector<int> decode(uint e)
{
	vector<int> res;
	for ( ; e; e >>= 4)
		res.push_back(e & 0xf);
	return res;
}
int main()
{
	int n, c[16][16];
	cin >> n;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			cin >> c[i][j];

	vector<int> ori;
	for (int i = 1; i <= n; ++i)
		ori.push_back(i);
	int ori_e = encode(ori);

	int res = 0;
	map<int, int> dis;
	priority_queue<iu, vector<iu>, greater<iu> > q;
	dis[ori_e] = 0;
	q.push(iu(0, ori_e));
	while (!q.empty())
	{
		iu t = q.top(); q.pop();
		int cost = t.first;
		uint e = t.second;
		if (cost > dis[e])
			continue;

		max_swap(res, cost);

		vector<int> v = decode(e);
		for (int i = 0; i < n; ++i)
		{
			for (int j = i + 1; j < n; ++j)
			{
				swap(v[i], v[j]);
				int nc = cost + c[v[i]][v[j]];
				uint ne = encode(v);
				swap(v[i], v[j]);

				if (!dis.count(ne) || nc < dis[ne])
				{
					dis[ne] = nc;
					q.push(iu(nc, ne));
				}
			}
		}
	}
	cout << res << endl;
}