#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
using namespace std;
typedef long long LL;
const int CN=25;
int N,G[CN][CN];
int f[1<<17][19][19][2];
template<typename T> inline bool chkmin(T &x,const T y){
	return (x>y)?(x=y,1):0;
}
int main(){

	scanf("%d",&N);
	for(int i=1;i<=N;++i){
		for(int j=1;j<=N;++j){
			scanf("%d",&G[i][j]);
		}
	}
	int ans=0;
	for(int i=1;i<=N;++i){
		for(int j=i+1;j<=N;++j){
			if(G[i][j]!=-1){
				int mn=min(G[i][j],G[j][i]);
				G[i][j]-=mn;
				G[j][i]-=mn;
				ans+=mn;
			}
		}
	}
	memset(f,0x3f,2888 << N);
	f[1][1][1][0]=0;
	f[1][1][1][1]=0;
	for(int s=1;s<(1<<N);++s){
		int mincost=1e9;
		for(int i=1;i<=N;++i){ // 从i开始
			for(int j=1;j<=N;++j){ // 需要到j
				int ho=f[s][i][j][0],ha=f[s][i][j][1];
				// 记得跳过没用的转移。。。
				if(ho>1e9&&ha>1e9){
					continue;
				}
				if(i!=j){
					for(int k=1;k<=N;++k){ // 现在把路径走向k
						// 从i走到k
						if(G[i][k]!=-1){
							if(((s>>(k-1))&1)==0||k==j){
								if(k!=j){
									chkmin(f[s|(1<<(k-1))][k][j][1],ho+G[i][k]);
								}
								chkmin(f[s|(1<<(k-1))][k][j][1],ha+G[i][k]);
							}
						}
					}
				}
			}
		}
		for(int i=1;i<=N;++i){ // 注意搞清楚转移顺序
			chkmin(mincost,f[s][i][i][1]);
			chkmin(mincost,f[s][i][i][0]);
		}
		if(mincost>=1e9){
			continue;
		}
		for(int k=1;k<=N;++k){
			if(((s>>(k-1))&1)==0){
				continue;
			}
			for(int i=1;i<=N;++i){
				if(((s>>(i-1))&1)||G[k][i]==-1){
					continue;
				}
				int hoha=s|(1<<(i-1));
				int tmp=G[k][i];
				for(int j=1;j<=N;++j){
					if(((s>>(j-1))&1)==0){
						continue;
					}
					if(k==j){
						chkmin(f[hoha][i][j][0],mincost+tmp);
					}else{
						chkmin(f[hoha][i][j][1],mincost+tmp);
					}
				}
			}
		}
	}
	int ans1=0x3f3f3f3f;
	for(int i=1;i<=N;++i){
		chkmin(ans1,f[(1<<N)-1][i][i][1]);
		chkmin(ans1,f[(1<<N)-1][i][i][0]);
	}
	if(ans1>=1e9){
		printf("-1\n");
	}else{
		printf("%d\n",ans+ans1);
	}
	return 0;
}