#include <cstdio>

#include <algorithm>

#include <cstring>

#include <climits>

using namespace std;

const int N();

int w[N][N];

int Lx[N], Ly[N], slack[N];

bool S[N], T[N];

int match[N];

int n;

bool dfs(int u)

{

    S[u]=true;

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

    {

        if(T[v])

        {

            continue;

        }

        int tmp=Lx[u]+Ly[v]-w[u][v];

        if(tmp==)

        {

            T[v]=true;

            if(!match[v] || dfs(match[v]))

            {

                match[v]=u;

                return true;

            }

        }

        else

        {

            slack[v]=min(slack[v], tmp);

        }

    }

    return false;

}

void KM()

{

    memset(match, , sizeof(match));

    memset(Lx, 0x3f, sizeof(Lx));

    memset(Ly, 0x3f, sizeof(Ly));

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

    {

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

        {

            slack[i]=INT_MAX;    //error-prone

        }

        for(int a; ;)

        {

            memset(S, , sizeof(S));

            memset(T, , sizeof(T));

            if(dfs(i)) break;

            a=INT_MAX;

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

            {

                if(!T[j])

                {

                    a=min(a, slack[j]);

                }

            }

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

            {

                if(S[j])

                {

                    Lx[j]-=a;

                }

                if(T[j])

                {

                    Ly[j]+=a;

                }

                else

                {

                    slack[j]-=a;

                }

            }

        }

    }

    int res=;

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

    {

        res+=w[match[i]][i];

    }

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

}

int main()

{

    for(; ~scanf("%d", &n); )

    {

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

        {

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

            {

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

            }

        }

        KM();

    }

}

slack[v]=min(slack[v], tmp);