#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
ifstream f("../cc.in");
ofstream g("../cc.out");
int n, nod_sursa, nod_final, dist;
vector<vector<int>> vecini, capacitati, flow, distanta;
vector<int> predecesor, distantaMin;
int res;

void citire_date () {
    f >> n;
    nod_final = 2 * n + 1;
    predecesor.resize(nod_final + 1);
    distantaMin.resize(nod_final + 1);
    vecini.resize(nod_final + 1, {});
    capacitati.assign(nod_final + 1, vector<int>(nod_final + 1, 0));
    flow.resize(nod_final + 1, vector<int>(nod_final + 1, 0));
    distanta.resize(nod_final + 1, vector<int>(nod_final + 1, 0));

    for (int i=1; i <= n; i++) {
        vecini[0].push_back(i);
        vecini[i].push_back(0);
        capacitati[0][i] = 1;

        for (int j=1; j <= n; j++) {
            f>>dist;
            vecini[i].push_back(j + n);
            vecini[j + n].push_back(i);
            capacitati[i][j + n] = 1;
            distanta[i][j + n] = dist;
            distanta[j + n][i] = -dist;
        }
    }

    for (int i=1; i <= n; i++) {
        vecini[i + n].push_back(nod_final);
        vecini[nod_final].push_back(i + n);
        capacitati[i + n][nod_final] = 1;
    }
}

int bfs () {
    for (int i=0; i <= nod_final; i++) {
        predecesor[i] = -1;
        distantaMin[i] = INT_MAX;
    }
    distantaMin[0] = 0;
    queue<pair<int, int>> q;
    q.push({0, INT_MAX});
    while (!q.empty()) {
        int nod_actual = q.front().first, min_flow_anterior = q.front().second;
        q.pop();
        for (auto& vecin : vecini[nod_actual]) {

            if (distantaMin[vecin] > distantaMin[nod_actual] + distanta[nod_actual][vecin] && capacitati[nod_actual][vecin] > flow[nod_actual][vecin]) {
                predecesor[vecin] = nod_actual;
                int min_flow_actual = capacitati[nod_actual][vecin] - flow[nod_actual][vecin];
                int min_flow;
                if(min_flow_actual > min_flow_anterior )
                    min_flow =min_flow_anterior;
                else
                    min_flow=min_flow_actual;
                distantaMin[vecin] = distantaMin[nod_actual] + distanta[nod_actual][vecin];
                q.push({vecin, min_flow});
            }
        }
    }

    return predecesor[nod_final] >= 0;
}

void edmonds_karp () {
    while (true) {
        int flow_min = bfs();

        if (!flow_min) break;
        int nod_actual = nod_final;
        while (nod_actual != 0) {
            int nod_anterior = predecesor[nod_actual];
            flow[nod_anterior][nod_actual] += flow_min;
            flow[nod_actual][nod_anterior] -= flow_min;
            nod_actual = nod_anterior;
        }
        res += distantaMin[nod_final];
    }
    g << res;
}

int main () {
    citire_date();
    edmonds_karp();
    return 0;
}