#include<iostream> #include<cstring> #include<ctime> using namespace std; #define memoryMB(x) (sizeof(x)>>20) #define timeMS (clock()*1000/CLOCKS_PER_SEC) const int N=17,inf=0x3f3f3f3f; int g[N][N]; int F[1<<N],G[1<<N][N][N][2]; int n,lim; int sum; void init(){ cin>>n; for(int i=0;i<n;i++){ for(int j=0;j<n;j++)cin>>g[i][j]; } for(int i=0;i<n;i++){ for(int j=0;j<i;j++)if(g[i][j]>=0){ int m=min(g[i][j],g[j][i]); sum+=m; g[i][j]-=m; g[j][i]-=m; } } lim=(1<<n); } signed main(){ // freopen("read.in","r",stdin); init(); // cout<<sum<<'\n'; // for(int i=0;i<n;i++){ // for(int j=0;j<n;j++)cout<<g[i][j]<<' '; // cout<<'\n'; // } memset(F,0x3f,sizeof(F)); memset(G,0x3f,sizeof(G)); for(int i=0;i<n;i++)F[1<<i]=0; for(int s=1;s<lim;s++){ for(int i=0;i<n;i++)if((s>>i)&1){ for(int j=0;j<n;j++)if(g[i][j]>=0&&((s>>j)&1)){ F[s]=min(F[s],G[s][i][j][1]+g[i][j]); } } for(int i=0;i<n;i++)if((s>>i)&1){ for(int j=0;j<n;j++)if((s>>j)&1){ for(int k=0;k<=n;k++)if(g[i][k]>=0&&!((s>>k)&1)){ if(i==j)G[s|(1<<k)][k][j][0]=min(G[s|(1<<k)][k][j][0],F[s]+g[i][k]); else G[s|(1<<k)][k][j][1]=min(G[s|(1<<k)][k][j][1],min(F[s],min(G[s][i][j][0],G[s][i][j][1]))+g[i][k]); } } } } if(F[lim-1]<inf)cout<<F[lim-1]+sum; else cout<<-1; // cerr<<'\n'; // cerr<<memoryMB(F)+memoryMB(G)<<'\n'; // cerr<<timeMS; return 0; }