#include<stdio.h>

#include<string.h>

#include<iostream>

#include<algorithm>

#include<math.h>

#define INF 0xfffffff

#define N 330

using namespace std;

int maps[N][N], visx[N], visy[N], used[N], lx[N], ly[N], s[N], n;

///visx[i]代表第i人是否在曾广路上，

///used[i]代表第i个村庄是否被占用；

///lx[],ly[]代表人和村庄的顶标；

bool Find(int u)

{

    visx[u] = ;

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

    {

        if(!visy[i] && lx[u]+ly[i] == maps[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] - maps[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(maps[i][j], lx[i]);///初始化人的顶标；

    }

    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 ans=;

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

    {

        ans+=maps[used[i]][i];

    }

    return ans;

}

int main()

{

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

    {

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

        {

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

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

        }

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

    }

    return ;

}