#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> per[1001][1001];
int n, nr, rez, p[1001];
int dist[1001], ant[1001], init[1001][1001];

void update(int n, int i) {
    while (ant[n] != -1) {
        per[ant[n]][n].first -= i;
        rez += i * init[ant[n]][n];
        per[n][ant[n]].first += i;
        rez -= i * init[n][ant[n]];
        n = ant[n];
    }
}

void initializeaza() {
    for (int i = 1; i <= n; i++) {
        x[0].push_back(i);
        x[i].push_back(0);
        per[0][i] = {1, 0};
        per[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);
        per[i + n][nr] = {1, 0};
        per[nr][i + n] = {0, 0};
        init[i + n][nr] = 0;
    }

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

void bfs(queue<int>& q) {
    while (!q.empty()) {
        int n = q.front();
        q.pop();
        for (int i : x[n])
            if (per[n][i].first > 0 && dist[i] > dist[n] + per[n][i].second) {
                ant[i] = n;
                dist[i] = dist[n] + per[n][i].second;
                q.push(i);
            }
    }
}

void maxim() {
    queue<int> q;
    vector<int>::iterator it;

    q.push(0);
    while (!q.empty()) {
        int n = q.front();
        q.pop();
        p[n] = 0;

        for (it = x[n].begin(); it != x[n].end(); it++)
            if (per[n][*it].first > 0 && dist[*it] > dist[n] + per[n][*it].second) {
                ant[*it] = n;
                dist[*it] = dist[n] + per[n][*it].second;
                if (p[*it] == 0) p[*it] = 1, q.push(*it);
            }
    }

    if (dist[nr] != 1e9) {
        while (dist[nr] != 1e9) {
            update(nr, 1);

            for (int i = 0; i <= nr; i++)
                for (it = x[i].begin(); it != x[i].end(); it++)
                    per[i][*it].second += dist[i] - dist[*it];

            fill(begin(dist), end(dist), 1e9);
            fill(begin(p), end(p), 0);
            dist[0] = 0;
            ant[0] = -1;
            q.push(0);
            bfs(q);
        }
    }
}

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

    initializeaza();

    fill(begin(dist), end(dist), 1e9);
    fill(begin(p), end(p), 0);
    ant[0] = -1;
    p[0] = 1;
    dist[0] = 0;

    queue<int> q;
    q.push(0);

    bfs(q);
    if (dist[nr] != 1e9)
        maxim();

    fout << rez;
    return 0;
}