#include<bits/stdc++.h> using namespace std; #define int long long const int MAXN=40; int n,m,tim,ans=1e18,a[MAXN][MAXN],zf[MAXN][MAXN]; struct Edge{ int v,nx; }edge[MAXN]; int h[MAXN],CNT; void init(){memset(h,-1,sizeof(h));CNT=0;} void add_side(int u,int v){edge[++CNT]={v,h[u]};h[u]=CNT;} int vis[MAXN]; void dgs(int now,int frm){ tim++;vis[now]=frm; if(tim>40000000)return; for(int i=h[now];i!=-1;i=edge[i].nx){ if(vis[edge[i].v]!=frm)dgs(edge[i].v,frm); } } bool check(){ for(int i=1;i<=n;i++)vis[i]=0; for(int i=1;i<=n;i++){ dgs(i,i); for(int j=1;j<=n;j++)if(vis[j]!=i)return 0; } return 1; } void dfs(int u,int v,int sum){ if(sum>=ans)return; if(tim>40000000)return; int nu,nv; if(u==n+1){ init(); for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){ if(zf[i][j]){ if(a[i][j]!=-1)add_side(i,j); } else{ if(a[j][i]!=-1)add_side(j,i); } } } if(check())ans=min(ans,sum); return; } tim++; if(v+1>u)nu=u+1,nv=1; else nu=u,nv=v+1; if(u==v||a[u][v]==-1||a[v][u]==-1){ if(a[u][v]!=-1)zf[u][v]=1; if(a[v][u]!=-1)zf[v][u]=1; dfs(nu,nv,sum+zf[u][v]*a[u][v]+zf[v][u]*a[v][u]); return; } if(a[u][v]<a[v][u]){ zf[u][v]=1; dfs(nu,nv,sum+zf[u][v]*a[u][v]+zf[v][u]*a[v][u]); zf[u][v]=0; zf[v][u]=1; dfs(nu,nv,sum+zf[u][v]*a[u][v]+zf[v][u]*a[v][u]); zf[v][u]=0; } else{ zf[v][u]=1; dfs(nu,nv,sum+zf[u][v]*a[u][v]+zf[v][u]*a[v][u]); zf[v][u]=0; zf[u][v]=1; dfs(nu,nv,sum+zf[u][v]*a[u][v]+zf[v][u]*a[v][u]); zf[u][v]=0; } } signed main(){ scanf("%lld",&n); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ scanf("%lld",&a[i][j]); } } dfs(1,1,0); if(ans==1e18)ans=-1; printf("%lld",ans); return 0; }