#include<stdio.h>
#include<string.h>

#define NMAX 25006
#define minim(a,b) (a<b ? a : b)
#define INF 1000000005

int x[NMAX],inv[NMAX],cost[NMAX];
int y[NMAX],cap[NMAX],f[NMAX],nr;
int n,pred[NMAX],dist[NMAX],rez;

int bellman()
{
    int i,j,ok=0;
    memset(pred,0,sizeof(pred));
    for(i=1;i<=2*n+1;i++)
        dist[i]=INF;
    for(i=1;i<n && !ok;i++)
    {
        ok=1;
        for(j=1;j<=nr;j++)
            if(cap[j]>f[j] && dist[x[j]]!=INF
            && dist[x[j]]+cost[j]<dist[y[j]])
            {
                dist[y[j]]=dist[x[j]]+cost[j];
                pred[y[j]]=j;
                ok=0;
            }
    }
    return dist[2*n+1]!=INF;
}


int main ()
{
    int i,j,sol;
    
    freopen("cc.in","r",stdin);
    freopen("cc.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        y[++nr]=i;
        cap[nr]=1;
        x[++nr]=i;
        inv[nr]=nr-1;
        inv[nr-1]=nr;
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            scanf("%d",&cost[++nr]);
            x[nr]=i;
            y[nr]=j+n;
            cap[nr]=1;
            y[++nr]=i;
            x[nr]=j+n;
            cost[nr]=-cost[nr-1];
            inv[nr]=nr-1;
            inv[nr-1]=nr;
        }
    for(i=1;i<=n;i++)
    {
        cap[++nr]=1;
        x[nr]=i+n;
        y[nr]=2*n+1;
        x[++nr]=2*n+1;
        y[++nr]=i+n;
        inv[nr]=nr-1;
        inv[nr-1]=nr;
    }
    while(bellman())
    {
        sol=INF;
        for(i=2*n+1;i!=0;i=x[pred[i]])
            sol=minim(sol,cap[pred[i]]-f[pred[i]]);
        rez+=dist[2*n+1];
        for(i=2*n+1;i!=0;i=x[pred[i]])
        {
            f[pred[i]]+=sol;            
            f[inv[pred[i]]]-=sol;
        }
    }
    printf("%d\n",rez);
    return 0;
}