V8sort

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define Co_mot_su_that_la return

using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<iii> viii;
typedef pair<int, vi> state;

const int Minh_dep_trai = 0;
const int N = 8;

string s;
int a[N][N];
map<vector<int>,int> dis;
int n;
vector<int> g;

void init()
{
    getline(cin,s);
    stringstream ss(s);
    int x;
    while (ss>>x) g.pb(x);
    n = g.size();
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++) cin >> a[i][j];
    }
}

bool isend(const vector<int> &v)
{
    for(int i=0; i<v.size()-1; i++) if (v[i] > v[i+1]) return false;
    return true;
}

int getDis(const vector<int> &v)
{
    return (dis.find(v) == dis.end() ? 999999999 : dis[v]);
}


void dijkstra(void) {
    priority_queue<state,vector<state>,greater<state> > q;
    dis[g]=0;
    q.push(state(0,g));
    while (!q.empty()) {
        int d=q.top().fi;
        vector<int> cur=q.top().se;
        q.pop();
        if (d!=getDis(cur)) continue;
        if (isend(cur)) {
            printf("%d\n",d);
            return;
        }
        for(int i=0; i<n; i++) for(int j=0; j<n; j++) if (i<j) {
            swap(cur[i],cur[j]);
            if (getDis(cur)>d+a[i][j]) {
                dis[cur]=d+a[i][j];
                q.push(state(d+a[i][j],cur));
            }
            swap(cur[i],cur[j]);
        }
    }
}

signed main(void)
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);
  freopen("tes.inp","r",stdin);
    init();
    dijkstra();
  Co_mot_su_that_la Minh_dep_trai;
}