/*

 其实在求最大 最小的时候只要用一个模板就行了,

 把边的权值去相反数即可得到另外一个.求结果的时候再去

 相反数即可,最大最小有一些地方不同。。

 */

 #include <iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 const int N = ;

 const int INF = (<<)-;

 int w[N][N];

 int lx[N],ly[N]; //顶标

 int linky[N],visx[N],visy[N],slack[N];

 int n;

 bool find(int x){

     visx[x]=;

     for(int y=;y<=n;y++){

         if(visy[y])continue;

         int t=lx[x]+ly[y]-w[x][y];

         if(t==){

             visy[y] = ;

             if(linky[y]==-||find(linky[y]))return linky[y]=x,;

         }

         else if(slack[y]>t)slack[y]=t;

     }

     return ;

 }

 int KM(){

     int i,j;

     memset(linky,-,sizeof(linky));

     memset(ly,,sizeof(ly));

     for(i=;i<=n;i++){

         lx[i]=-INF;

          for(j = ;j<=n;j++)

             if(w[i][j]>lx[i])lx[i]=w[i][j];

     }

     for(int x=;x<=n;x++){

         for(i=;i<=n;i++)slack[i]=INF;

         while(){

             memset(visx,,sizeof(visx));

             memset(visy,,sizeof(visy));

             if(find(x))break;//找到增广轨，退出

             int d=INF;

             for(i=;i<=n;i++) //没找到，对l做调整(这会增加相等子图的边)，重新找

             if(!visy[i]&&d>slack[i])d=slack[i];

             for(i=;i<=n;i++)if(visx[i])lx[i]-=d;

             for(i=;i<=n;i++)

                 if(visy[i])ly[i]+=d;else slack[i]-=d;

         }

     }

     int result = ;

     for(i=;i<=n;i++)if(linky[i]>-)result+=w[linky[i]][i];

     return result;

 }

 int main()

 {

     while(scanf("%d",&n)==)

     {

         int cost;

         for(int i=;i<=n;i++)

         for(int j=;j<=n;j++)

         {

             scanf("%d",&cost);

             w[i][j]=cost;

         }

         printf("%d\n",KM());

     }

     return ;

 }