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 <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>

using namespace std;

const int INF = 1001001001;
const int MOD = 1000000007;


vector<int> dijk(int s, int v, vector<vector<pair<int, int> > > adjlist){
    
    priority_queue <pair<int, int> > wait;
    vector<int> result(v, INF);

    //スタート地点を追加
    result[s] = 0;
    wait.push(make_pair(0, s));

    //ダイクストラ本体
    while(!wait.empty()){    //waitが空になるまで

        int nowpoint = wait.top().second;
        int nowcost = -wait.top().first;
        wait.pop();

        if(result[nowpoint] < nowcost) continue;

        //今いる頂点と隣接しているすべての頂点をなめる
        for(int i = 0; i < adjlist[nowpoint].size(); i++){

            int nextpoint = adjlist[nowpoint][i].second;
            int nextcost = nowcost + adjlist[nowpoint][i].first;
            //現時点より安く到達できそうであれば、結果を更新して優先度付きキューに格納
            if(result[nextpoint] > nextcost){
                result[nextpoint] = nextcost;
                wait.push(make_pair(-nextcost, nextpoint));
            }
        }
    }
    
    return result;         //結果列を返す
}

signed main(){
    
    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];
    map<vector<int>, int> m;
    int cnt = 0;
    vector<int> v(n);
    for(int i = 0; i < n; i++){
        v[i] = i;
    }

    do{
        m[v] = cnt;
        cnt++;
    }while(next_permutation(v.begin(), v.end()));
    

    vector<vector<pair<int, int> > > G(cnt);
    sort(v.begin(), v.end());


    do{
        int cur = m[v];
        for(int i = 0; i < n; i++){
            for(int j = i; j < n; j++){
                swap(v[i], v[j]);
                int cost = c[v[i]][v[j]];
                int nxt = m[v];
                G[cur].push_back({cost, nxt});
                G[nxt].push_back({cost, cur});
                swap(v[i], v[j]);
            }
        }

    }while(next_permutation(v.begin(), v.end()));

    vector<int> result = dijk(0, cnt, G);
    int ans = 0;
    for(int i = 0; i < cnt; i++){
        ans = max(ans, result[i]);
    }
    cout << ans << endl;
    return 0;
}


