#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream fin("cc.in");
ofstream fout("cc.out");

vector<int> x[1001];
pair<int, int> h[1001][1001];
[[maybe_unused]] int n, nr, sol, p[1001];
[[maybe_unused]] int dist[1001], prec[1001], init[1001][1001];

void initializeNodes() {
    for (int i = 1; i <= n; i++) {
        x[0].push_back(i);
        x[i].push_back(0);
        h[0][i] = {1, 0};
        h[i][0] = {0, 0};
        init[0][i] = 0;
    }

    for (int i = 1; i <= n; i++) {
        x[i + n].push_back(nr);
        x[nr].push_back(i + n);
        h[i + n][nr] = {1, 0};
        h[nr][i + n] = {0, 0};
        init[i + n][nr] = 0;
    }
}

void readEdgeCapacities() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            fin >> h[i][j + n].second;
            x[i].push_back(j + n);
            x[j + n].push_back(i);
            h[i][j + n].first = 1;
            h[j + n][i] = {0, -h[i][j + n].second};
        }
}

void bfs() {
    fill(begin(dist), end(dist), 1e9);
    dist[0] = 0;
    queue<int> q({0});

    while (!q.empty()) {
        int a = q.front(); q.pop();
        for (int i : x[a])
            if (h[a][i].first > 0 && dist[i] > dist[a] + h[a][i].second)
                prec[i] = a, dist[i] = dist[a] + h[a][i].second, q.push(i);
    }
}

void updateGraph() {
    while (dist[nr] != 1e9) {
        while (prec[nr] != -1) {
            h[prec[nr]][nr].first--;
            sol += h[prec[nr]][nr].second;
            h[nr][prec[nr]].first++;
            sol -= h[nr][prec[nr]].second;
            nr = prec[nr];
        }
        
        for (int i = 0; i <= nr; i++)
            for (int j : x[i])
                h[i][j].second += dist[i] - dist[j];

        bfs();
    }
}

int main() {
    fin >> n;
    nr = n + n + 1;

    initializeNodes();
    readEdgeCapacities();
    bfs();

    if (dist[nr] != 1e9)
        updateGraph();

    fout << sol;
    return 0;
}