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

typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef pair<int,int> pint;

#define DE 1
#define FI first
#define SE second
#define PB push_back
#define MP make_pair
#define ALL(s) (s).begin(),(s).end()
#define REP(i,n) for (int i = 0; i < (int)(n); ++i)
#define EACH(i,s) for (typeof((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define COUT(x) cout<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<<endl

template<class T1, class T2> ostream& operator<<(ostream &s, pair<T1,T2> P){return s<<'<'<<P.first<<", "<<P.second<<'>';}
template<class T> ostream& operator<<(ostream &s, vector<T> P) {s<<"{ ";for(int i=0;i<P.size();++i){if(i>0)s<<", ";s<<P[i];}return s<<" }"<<endl;}
template<class T1, class T2> ostream& operator<<(ostream &s, map<T1,T2> P) {s<<"{ ";for(typeof(P.begin()) it=P.begin();it!=P.end();++it){if(it!=P.begin())s<<", ";s<<'<'<<it->first<<"->"<<it->second<<'>';}return s<<" }"<<endl;}



int N;
int cost[10][10];
map<vint,int> dp;
map<vint,bool> seen;

int main() {
    //freopen( "/Users/macuser/Documents/Programming/Contest/input.in", "r", stdin );
    
    while (cin >> N) {
        int c;
        memset(cost, 0, sizeof(cost));
        for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) {
            cin >> c;
            cost[i+1][j+1] = c;
        }
        
        vint start(N);
        for (int i = 0; i < N; ++i) start[i] = i+1;
        
        dp.clear();
        seen.clear();
        dp[start] = 0;
        seen[start] = true;
        priority_queue<pair<int,vint>, vector<pair<int,vint> >, greater<pair<int,vint> > > que;
        que.push(MP(0,start));
        
        while (!que.empty()) {
            vint now = que.top().SE;
            int nowcost = que.top().FI;
            que.pop();
            
            if (dp[now] < nowcost) continue;
            
            for (int i = 0; i < N; ++i) {
                for (int j = i+1; j < N; ++j) {
                    vint nnow = now;
                    swap(nnow[i], nnow[j]);
                    int dist = dp[now] + cost[now[i]][now[j]];
                    
                    if (!seen[nnow]) {
                        que.push(MP(dist,nnow));
                        dp[nnow] = dist;
                        seen[nnow] = true;
                    }
                    else {
                        if (dist < dp[nnow]) {
                            dp[nnow] = dist;
                            que.push(MP(dist,nnow));
                        }
                    }
                }
            }
            
            //cout << now << " : " << dp[now] << endl;
        }
        
        int res = 0;
        EACH(it,dp) res = max(res, it->SE);
        
        cout << res << endl;
    }
    
    return 0;
}
