TAXI

#include <stdio.h>
#define maxn 25
#define MODULO 1000000007

int n;
int m;
int a[maxn][maxn];
bool f[maxn];           // da danh dau?
int minq = 1000000000;
int q;
int sol[maxn];              // nghiem

void input () {
    scanf("%d", &n);
    m = n;
    n /= 2;
    for (int i = 0; i <= m; ++i) {
        for (int j = 0; j <= m; ++j) {
            scanf("%d", &a[i][j]);
        }
        sol[i] = 0;
        f[i] = false;
    }
    f[0] = true;
    q = 0;
}

void output () {
    printf("%d", minq);
}


bool check (int i, int k) {
    if (f[i])           // da danh dau
        return false;
    if (q >= minq)      // quang duong hien tai da >= gia tri nho nhat
        return false;
    if (i >= n && f[i-n] == false)
        return false;
    return true;
}

void attempt (int k) {
    for (int i = 1; i <= m; ++i) {
        if (check(i, k)) {          // thoa man chua danh dau va quang duong < q
            f[i] = true;
            sol[k] = i;
            q += a[sol[k-1]][sol[k]];
            if (k == m) {
                q += a[i][0];
                if (q < minq) {
                    minq = q;
                    // output();
                }
                q -= a[i][0];
            } else {
                attempt(k+1);
            }
            f[i] = false;
            q -= a[sol[k-1]][sol[k]];
        }
    }
}

void solve () {
    attempt(1);
}

int main () {
    input();
    solve();
    output();
    return 0;
}