#include<iostream>
#include<fstream>
#include <vector>
#include <cstring>
#include <queue>
#define inf 2147000000
using namespace std;
ifstream f("cc.in");
ofstream g("cc.out");
 struct node
 { int nod,cost;} el;

 struct cmp
 {
  bool operator() (node x,node y)
  {return x.cost>y.cost;}
 };

 priority_queue <node, vector<node>, cmp> heap;
 vector <int> v[205];
 queue <int> q;
 int n,s,d,sol=0,cst[205][205],c[205][205],fol[205][205],dmin[205],dmin2[205],ant[205],reald[205],use[205];

void BellmanFord()
{ int i,nod,nod2,newc;
    memset(use,0,sizeof(use));

    for(i=1;i<=2*n+2;i++)
     dmin[i]=inf;

    q.push(s); dmin[s]=0;

    while(!q.empty())
    { nod=q.front(); q.pop();
        use[nod]=0;

       for(i=0;i<v[nod].size();i++)
       { nod2=v[nod][i];
           newc=dmin[nod]+cst[nod][nod2];
          if (c[nod][nod2] && newc<dmin[nod2])
          { dmin[nod2]=newc;
            if (use[nod2]) continue;
            q.push(nod2); use[nod2]=1;
          }
       }
    }
}

int Dijkstra()
{ int i,x,nod,nod2,cost,newc,res;

    for(i=1;i<=2*n+2;i++)
    { ant[i]=0;
      dmin2[i]=inf;
      reald[i]=inf;
    }

    el.nod=s; dmin2[s]=0; reald[s]=0;

     el.cost=0;
      heap.push(el);

     while(!heap.empty())
     { el=heap.top(); heap.pop();
        nod=el.nod; cost=el.cost;
        if (cost!=dmin2[nod] || nod==d) continue;

        for(i=0;i<v[nod].size();i++)
        { nod2=v[nod][i];
          if (c[nod][nod2]==fol[nod][nod2]) continue;
          newc=dmin2[nod]+dmin[nod]+cst[nod][nod2]-dmin[nod2];

          if (newc<dmin2[nod2])
          { dmin2[nod2]=newc;
            el.nod=nod2; el.cost=dmin2[nod2];
            heap.push(el);
            reald[nod2]=reald[nod]+cst[nod][nod2];
            ant[nod2]=nod;
          }
        }
     }

 if (reald[d]==inf)
     return 0;

   memcpy(dmin,reald,sizeof(dmin));

    x=d; res=inf;
     while(ant[x])
     { res=min(res,c[ant[x]][x]-fol[ant[x]][x]);
       x=ant[x];
     }

   sol+=res*reald[d];

    x=d;

    while(ant[x])
    { fol[ant[x]][x]+=res;
      fol[x][ant[x]]-=res;
       x=ant[x];
    }

 return 1;
}
int main()
{ int i,j,ok;
   f>>n;
    s=2*n+1; d=2*n+2;

   for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
     {
       f>>cst[i][j+n];
       cst[j+n][i]=-cst[i][j+n];
       v[i].push_back(j+n);
       v[j+n].push_back(i);
       c[i][j+n]=1;
     }

   for(i=1;i<=n;i++)
   { v[s].push_back(i);
     c[s][i]=1;
     v[n+i].push_back(d);
     c[n+i][d]=1;
   }

    BellmanFord();

    do {ok=Dijkstra();} while(ok);

   g<<sol;

  return 0;
}