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 <iomanip>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <climits>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1<<29;
const double PI = acos(-1);
const double EPS = 1e-8;

typedef long long ll;

int N;
int c[8][8];

struct P {
  int v[8]; 
  int dist;
  P(int a[], int dist) : dist(dist) {
    REP(i,N)v[i]=a[i];
  }
  P() {}
};

struct P2 {
  int v[8];
  P2(int a[]) {
    REP(i, N) v[i] = a[i];
  }
  P2() {}
};

bool operator<(const P &a, const P &b) {
  return a.dist > b.dist;
}

bool operator<(const P2 &a, const P2 &b) {
  REP(i, N) if (a.v[i]!=b.v[i]) return a.v[i]<b.v[i];
  return 0;
}
				 

int main() {
  cin >> N;
  REP(i, N) {
    REP(j, N) {
      cin >> c[i][j];
    }
  }
  priority_queue<P> Q;
  int ini[8];
  REP(i,N) ini[i] = i;
  Q.push(P(ini, 0));
  map<P2, int> dist;
  dist[P2(ini)] = 0;
  int ans = 0;
  while(!Q.empty()) {
    P p = Q.top(); Q.pop();
    if (p.dist > dist[P2(p.v)]) continue; 
    ans = max(ans, p.dist);
//     REP(i, N) cout << p.v[i] << " ";cout <<endl;
//     cout << p.dist << " " << dist[P2(p.v)] << endl;
    REP(i, N) {
      REP(j, i) {
	int tmp[N];
	REP(k, N) tmp[k] = p.v[k];
	swap(tmp[i], tmp[j]);
	int d = p.dist + c[p.v[i]][p.v[j]];
	if (dist.count(P2(tmp)) == 0 || dist[P2(tmp)] > d) {
	  dist[P2(tmp)] = d;
	  Q.push(P(tmp, d));
	}
      }
    }
  }
  cout << ans << endl;
}