#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define uint unsigned
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = (1 << 18) + 50;

int n, a[19][19], f[maxn], g[maxn][19][19][2];

void solve() {
	scanf("%d", &n);
	mems(f, 0x3f);
	mems(g, 0x3f);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			scanf("%d", &a[i][j]);
		}
	}
	int s = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			if (a[i][j] != -1) {
				s += min(a[i][j], a[j][i]);
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		f[1 << i] = s;
	}
	for (int S = 1; S < (1 << n); ++S) {
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				for (int o = 0; o <= 1; ++o) {
					int v = g[S][i][j][o];
					if (v > 1e9) {
						continue;
					}
					for (int k = 0; k < n; ++k) {
						if ((S & (1 << k)) || a[i][k] == -1) {
							continue;
						}
						g[S | (1 << k)][k][j][0] = min(g[S | (1 << k)][k][j][0], v + a[i][k] - min(a[i][k], a[k][i]));
					}
				}
				if (a[i][j] != -1) {
					f[S] = min(f[S], g[S][i][j][0] + a[i][j] - min(a[i][j], a[j][i]));
				}
			}
		}
		for (int i = 0; i < n; ++i) {
			if ((~S) & (1 << i)) {
				continue;
			}
			for (int j = 0; j < n; ++j) {
				if ((~S) & (1 << j)) {
					continue;
				}
				for (int k = 0; k < n; ++k) {
					if ((S & (1 << k)) || a[i][k] == -1) {
						continue;
					}
					g[S | (1 << k)][k][j][i == j] = min(g[S | (1 << k)][k][j][i == j], f[S] + a[i][k] - min(a[i][k], a[k][i]));
				}
			}
		}
	}
	printf("%d\n", f[(1 << n) - 1] > 1e9 ? -1 : f[(1 << n) - 1]);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}