#include <algorithm>
#include <fstream>
#include <cstring>
#include <queue>

#define se second
#define fi first

#define INF 10000000
#define DIM 500

using namespace std;

ifstream f ("cc.in");
ofstream g ("cc.out");

int dmin[DIM] , c[DIM][DIM] , flow[DIM][DIM] , cst[DIM][DIM] , t[DIM] , qw[DIM];
int n , cost , flux , D , tcost;

vector <pair <int , int> > G[DIM];

class comp {
public:
    bool operator()(int& t1, int& t2){
       return dmin[t1] > dmin[t2];
    }
};priority_queue <int, std::vector<int>, comp> coada;

bool dijkstra();

int main() {
    f >> n;
    for (int i = 2; i <= n + 1; ++i) {
        c[1][i] = 1;
        G[1].push_back (make_pair (i , 0));
        G[i].push_back (make_pair (1 , 0));
    }

    D = 2 * n + 2;
    for (int i = n + 2; i <= 2 * n + 1; ++i) {
        c[i][D] = 1;
        G[i].push_back (make_pair (D , 0));
        G[D].push_back (make_pair (i , 0));
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            f >> cost;
            int x = i + 1, y = j + n + 1;
            c[x][y] = 1;

            G[x].push_back (make_pair (y , cost));
            G[y].push_back (make_pair (x , cost));
            cst[x][y] = cost;
            cst[y][x] = 0;
        }
    }

    while (dijkstra ()) {
        int nr = G[D].size();
        for (int i = 0; i < nr; ++i) {
            int x = G[D][i].fi;
            if (flow[x][D] < c[x][D] && t[x]) {
                int u = x , val = c[x][D] - flow[x][D];
                while(u != 1) {
                    val = min(val , c[t[u]][u] - flow[t[u]][u]);
                    u = t[u];
                }

                u = x;
                flow[x][D] += val;
                flow[D][x] -= val;

                while(u != 1)
                {
                    flow[t[u]][u] += val;
                    flow[u][t[u]] -= val;
                    u = t[u];
                }

                flux += val;
            }
        }
    }

    for (int i = 1; i <= D; ++i) {
        for (int j = i + 1; j <= D; ++j) {
            if (flow[i][j]) {
                tcost += cst[i][j];
            }
        }
    }
    g << tcost;
    return 0;
}

bool dijkstra () {
    fill (dmin , dmin + D + 1 , INF);
    memset (t , 0 , sizeof (t));
    memset (qw , 0 , sizeof (qw));
    coada.push(1);
    dmin[1] = 0;

    while (!coada.empty()) {
        int node = coada.top();
        coada.pop();

        int nr = G[node].size ();
        for (int i = 0; i < nr; ++i) {
            int x = G[node][i].fi;
            if (!t[x] && flow[node][x] < c[node][x] && dmin[x] > dmin[node] + G[node][i].se) {
                dmin[x] = dmin[node] + G[node][i].se;
                coada.push (x);
                t[x] = node;
            }
        }
    }

    int p = D;
    while (p) {
        qw[p] = 1;
        p = t[p];
    }

    for (int i = 1; i <= D; ++i) {
        if (!qw[i]) {
            t[i] = 0;
        }
    }
    if (dmin[n] != INF)
        return 1;
    return 0;
}