#include <algorithm>

 #include <string.h>

 #include <iostream>

 #include <cstdio>

 using namespace std;

 /* KM算法

 * 复杂度O(nx*nx*ny)

 * 求最大权匹配

 * 若求最小权匹配，可将权值取相反数，结果取相反数

 * 点的编号从0开始

 */

 const int N = ;

 const int INF = 0x3f3f3f3f;

 int nx,ny; //两边的点数

 int W[N][N]; //二分图描述

 int Left[N],Lx[N],Ly[N]; //y中各点匹配状态， x,y中的点标号

 int slack[N];

 bool S[N],T[N];

 bool DFS(int x) {

     S[x] = true;

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

         if(T[y]) continue;

         int tmp = Lx[x] + Ly[y] - W[x][y];

         if(tmp == ){

             T[y] = true;

             if(Left[y] == - || DFS(Left[y])){

                 Left[y] = x;

                 return true;

             }

         }

         else if(slack[y] > tmp)

         slack[y] = tmp;

     }

     return false;

 }

 int KM(){

     memset(Left, -, sizeof(Left));

     memset(Ly,, sizeof(Ly));

     for(int i = ;i < nx;i++){

     Lx[i] = -INF;

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

         if(W[i][j] > Lx[i])

             Lx[i] = W[i][j];

     }

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

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

             slack[i] = INF;

         while(true){

             memset(S, false, sizeof(S));

             memset(T, false, sizeof(T));

             if(DFS(x)) break;

             int d = INF;

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

             if(!T[i] && d > slack[i])

             d = slack[i];

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

                 if(S[i])

             Lx[i] -= d;

             for(int i = ;i < ny;i++){

                 if(T[i])Ly[i] += d;

                 else slack[i] -= d;

             }

         }

     }

     int res = ;

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

         if(Left[i] != -)

             res += W[Left[i]][i];

     return res;

 }

 //HDU 2255

 int main()

 {

     int n;

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

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

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

            scanf("%d",&W[i][j]);

         nx = ny = n;

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

     }

     return ;

 }