#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define N 550

#define INF 0x3f3f3f3f

int n;

int G[N][N], lx[N], ly[N];//x集合的顶标

int visx[N], visy[N], s[N], used[N];//s是为了找d， visx[i]x中的i有没有被增广过

bool Find(int u)//增广路

{

    visx[u] = ;

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

    {

        if(!visy[i] && lx[u]+ly[i]==G[u][i])

        {

            visy[i]=;

            if(!used[i] || Find(used[i]))

            {

                used[i] = u;

                return true;

            }

        }

        else

            s[i] = min(s[i], lx[u]+ly[i]-G[u][i]);

    }

    return false;

}

int KM()

{

    memset(used, , sizeof(used));

    memset(lx, , sizeof(lx));

    memset(ly, , sizeof(ly));

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

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

    lx[i] = max(lx[i], G[i][j]);

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

    {

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

            s[j] = INF;

        while()

        {

            memset(visx, , sizeof(visx));

            memset(visy, , sizeof(visy));

            if(Find(i))

                break;

            int d = INF;

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

                if(!visy[j])

                    d = min(d, s[j]);

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

            {

                if(visx[j])

                    lx[j] -= d;

                if(visy[j])

                    ly[j] += d;

            }

        }

    }

    int res=;

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

        res += G[used[i]][i];

    return res;

}

int main()

{

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

    {

        int i, j;

        memset(G, , sizeof(G));

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

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

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

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

    }

    return ;

}