#include<iostream>

#include <cstdio>

#include <string.h>

#define inf 0x3f3f3f3f

#define N 310

using namespace std;

int n,nx,ny;   //nx,ny分别表示x集合和y集合的元素个数

int lx[N],ly[N],link[N],slack[N],visx[N],visy[N],w[N][N];

bool DFS(int x)

{

    int y;

    visx[x]=;

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

    {

        if(visy[y]) continue;

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

        if(t==)

        {

            visy[y]=;

            if(link[y]==-||DFS(link[y]))

            {

                link[y]=x;

                return true;

            }

        }

        else if(slack[y]>t)         //不在相等子图中slack 取最小的

            slack[y]=t;

    }

    return false;

}

int KM()

{

    int i,j,x;

    memset(link,-,sizeof(link));

    memset(ly,,sizeof(ly));

    for(i=;i<=nx;i++)            //lx初始化为与它关联边中最大的

        for(j=,lx[i]=-inf;j<=ny;j++)

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

                lx[i]=w[i][j];

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

    {

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

            slack[i]=inf;

        while()

        {

            memset(visx,,sizeof(visx));

            memset(visy,,sizeof(visy));

            if(DFS(x)) break;        //若成功（找到了增广轨），则该点增广完成，进入下一个点的增广

            //若失败（没有找到增广轨），则需要改变一些点的标号，使得图中可行边的数量增加。

            //方法为：将所有在增广轨中（就是在增广过程中遍历到）的X方点的标号全部减去一个常数d，

            //所有在增广轨中的Y方点的标号全部加上一个常数d

            int d=inf;

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

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

                   d=slack[i];

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

                if(visx[i])

                   lx[i]-=d;

            for(i=;i<=ny;i++)      //修改顶标后，要把所有不在交错树中的Y顶点的slack值都减去d

            {

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

                else        slack[i]-=d;

            }

        }

    }

    int ans=;

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

       if(link[i]>-)

          ans+=w[link[i]][i];

    return ans;

}

int main()

{

    int i,j;

    while(cin>>n)

    {

        nx=ny=n;

        memset(w,,sizeof(w));

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

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

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

        int ans=KM();

        cout<<ans<<endl;

    }

    return ;

}