#include <bits/stdc++.h> using namespace std; #define int long long #define endl "\n" #define lc(x) ((x) << 1) #define rc(x) ((x) << 1 | 1) //#define double long double #define pii pair<int,int> #define p1(x) ((x).first) #define p2(x) ((x).second) int n; int G[20][20]; bool p[20][20]; int g[1<<11][11][11]; int f[1<<11]; inline int ppc(int x){ return __builtin_popcount(x); } inline void chkmn(int &x,int y){ x=min(x,y); } inline int BF(){ int res=0; int N=1<<n; for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(G[i][j]!=1e13){ if(G[i][j]<G[j][i]) G[j][i]-=G[i][j],res+=G[i][j],G[i][j]=0; else G[i][j]-=G[j][i],res+=G[j][i],G[j][i]=0; } memset(f,0x3f,sizeof(f)); memset(g,0x3f,sizeof(g)); for(int i=0;i<n;i++) g[1<<i][i][i]=0; for(int S=0;S<N;S++) for(int i=0;i<n;i++) if(S&(1<<i)) for(int j=0;j<n;j++) if(S&(1<<j)) for(int k=0;k<n;k++) if(!(S&(1<<k))) chkmn(g[S|(1<<k)][i][k],g[S][i][j]+G[j][k]); f[1]=0; for(int S=0;S<N;S++){ for(int T=(N-1)^S;T;T--,T&=(N-1)) for(int i=0;i<n;i++) if(S&(1<<i)){ for(int j=0;j<n;j++) if(S&(1<<j)) chkmn(f[S|T],f[S]+g[T|(1<<i)|(1<<j)][i][j]); else if(ppc(T)>=2) chkmn(f[S|T],f[S]+g[T|(1<<i)][i][j]+G[j][i]); } } if(f[N-1]>=1e9)return -1; else return res+f[N-1]; } vector<int>gr[21]; bool vis[21]; int ct=0; inline void dfs(int u){ vis[u]=1; for(int v:gr[u]) if(!vis[v])dfs(v); ct++; } inline int chk(){ for(int i=0;i<n;i++){ memset(vis,0,sizeof(vis)); ct=0; dfs(i); if(ct!=n)return 0; } return 1; } vector<pii>E; int res=1e18; inline void dfs(int dep,int now){ if(now>res)return ; if(dep==E.size()){ if(chk()) res=min(res,now); return ; } int a=p1(E[dep]),b=p2(E[dep]); gr[a].push_back(b); dfs(dep+1,now+G[a][b]); gr[a].pop_back(); gr[b].push_back(a); dfs(dep+1,now+G[b][a]); gr[b].pop_back(); } inline int BF2(){ for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(p[i][j])E.push_back({i,j}); dfs(0,0); if(res>=1e12)return -1; return res; } signed main(){ ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); // freopen("s4.in","r",stdin); //freopen("anatomy.in", "r", stdin); //freopen("anatomy.out", "w", stdout); cin>>n; int ct=0; for(int i=0;i<n;i++) for(int j=0;j<n;j++){ cin>>G[i][j],ct+=p[i][j]=G[i][j]!=-1; if(!p[i][j]) G[i][j]=1e13; } int res=0; if(ct<=40)cout<<BF2()<<endl; else{ for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(G[i][j]!=1e13){ if(G[i][j]<G[j][i]) G[j][i]-=G[i][j],res+=G[i][j],G[i][j]=0; else G[i][j]-=G[j][i],res+=G[j][i],G[j][i]=0; } cout<<res<<endl; } cout.flush(); return 0; }