#include<iostream>
#include<cstdio>
#define N 18
#define inf 1e9
using namespace std;
int read()
{
    char c=0;
    int sum=0,f=1;
    while ((c<'0'||c>'9')&&c!='-') c=getchar();
    if (c=='-') c=getchar(),f=-1;
    while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
    return sum*f;
}
int n,dp[1<<N],S[1<<N][N+1][N+1],c[N+1][N+1],a[N+1][N+1],ans;
void Adder(int &x,int d)
{
    if (d<x) x=d;
    return;
}
int main()
{
    int d,res;
    n=read();
    for (int i=1;i<=n;++i)
	for (int j=1;j<=n;++j)
	    c[i][j]=read();
    for (int i=1;i<=n;++i)
	for (int j=i;j<=n;++j)
	{
	    d=min(c[i][j],c[j][i]);
	    if (c[i][j]==-1&&c[j][i]==-1) a[i][j]=a[j][i]=-1;
	    else if (c[i][j]!=-1&&c[j][i]==-1) ans+=c[i][j],a[i][j]=0,a[j][i]=-1;
	    else if (c[i][j]==-1&&c[j][i]!=-1) ans+=c[j][i],a[i][j]=-1,a[j][i]=0;
	    else ans+=d,a[i][j]=c[i][j]-d,a[j][i]=c[j][i]-d;
	}
    for (int i=0;i<(1<<n);++i) dp[i]=inf;
    for (int i=0;i<(1<<n);++i)
	for (int j=1;j<=n;++j)
	    for (int k=1;k<=n;++k)
		S[i][j][k]=inf;
    for (int i=1;i<=n;++i) dp[1<<(i-1)]=0;
    for (int i=0;i<(1<<n);++i)
    {
	for (int j=1;j<=n;++j)
	    if (i&(1<<(j-1)))
		for (int k=1;k<=n;++k)
		    if ((i&(1<<(k-1)))&&a[k][j]!=-1)
			Adder(dp[i],S[i][j][k]+a[k][j]);
	for (int j=1;j<=n;++j)
	    if (!(i&(1<<(j-1))))
		for (int k=1;k<=n;++k)
		    if (!(i&(1<<(k-1)))&&a[j][k]!=-1)
		    {
			res=inf;
	                for (int t=1;t<=n;++t)
			    if (i&(1<<(t-1))&&a[t][j]!=-1)
				Adder(res,dp[i]+a[t][j]+a[j][k]);
			for (int t=1;t<=n;++t)
			    if (i&(1<<(t-1)))
				Adder(S[i|(1<<(j-1))|(1<<(k-1))][t][k],res);
		    }
	for (int j=1;j<=n;++j)
	    if (i&(1<<(j-1)))
		for (int k=1;k<=n;++k)
		    if ((!(i&(1<<(k-1))))&&a[j][k]!=-1)
			for (int t=1;t<=n;++t)
			    if ((i&(1<<(t-1)))&&j!=t&&a[k][t]!=-1)
				Adder(dp[i|(1<<(k-1))],dp[i]+a[j][k]+a[k][t]);
	for (int j=1;j<=n;++j)
	    if (i&(1<<(j-1)))
		for (int k=1;k<=n;++k)
		    if (i&(1<<(k-1)))
			for (int t=1;t<=n;++t)
			    if ((!(i&(1<<(t-1))))&&a[k][t]!=-1)
				Adder(S[i|(1<<(t-1))][j][t],S[i][j][k]+a[k][t]);
    }
    printf("%d\n",(dp[(1<<n)-1]==inf)?-1:dp[(1<<n)-1]+ans);
    return 0;
}