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

using namespace std;

ifstream fin("cc.in");  // Flux de intrare din fișierul "cc.in"
ofstream fout("cc.out");  // Flux de ieșire în fișierul "cc.out"

int N, source, sink, totalDistance;
vector<vector<int>> graph, capacity, flow, distanceMatrix;
vector<int> previousNode, minDistance;

// Funcție pentru parcurgerea în lățime (BFS) pentru găsirea unui drum de la sursă la destinație
int bfs() {
    // Inițializarea vectorilor pentru nodurile precedente și distanța minimă
    previousNode.assign(sink + 1, -1);
    minDistance.assign(sink + 1, INT_MAX);
    minDistance[0] = 0;  // Distanța de la sursă la sursă este 0

    queue<pair<int, int>> q;
    q.push({0, INT_MAX});  // Adăugarea nodului sursă în coadă cu capacitatea maximă inițială

    while (!q.empty()) {
        int current = q.front().first, minFlowUntilNow = q.front().second;
        q.pop();

        // Parcurgerea vecinilor nodului curent
        for (auto &next : graph[current]) {
            // Verificarea dacă există o capacitate reziduală și dacă distanța minimă poate fi actualizată
            if (minDistance[next] > minDistance[current] + distanceMatrix[current][next] && capacity[current][next] > flow[current][next]) {
                previousNode[next] = current;
                int residualCapacity = capacity[current][next] - flow[current][next];
                int nextMinFlow = residualCapacity > minFlowUntilNow ? minFlowUntilNow : residualCapacity;
                minDistance[next] = minDistance[current] + distanceMatrix[current][next];
                q.push({next, nextMinFlow});
            }
        }
    }

    // Returnează true dacă a fost găsit un drum de la sursă la destinație
    return previousNode[sink] >= 0;
}

// Algoritmul Edmonds-Karp pentru găsirea fluxului maxim și a distanței minime
void edmondsKarp() {
    while (true) {
        int flowOfPath = bfs();

        // Dacă nu mai există drumuri augmentate, se oprește
        if (!flowOfPath) break;

        int current = sink;
        // Refacerea drumului și actualizarea fluxului pe tot traseul
        while (current != 0) {
            int previous = previousNode[current];
            flow[previous][current] += flowOfPath;
            flow[current][previous] -= flowOfPath;
            current = previous;
        }

        // Adăugarea la distanța totală
        totalDistance += minDistance[sink];
    }
}

int main() {
    // Citirea datelor de intrare
    fin >> N;
    sink = 2 * N + 1;
    previousNode.resize(sink + 1);
    minDistance.resize(sink + 1);
    graph.resize(sink + 1, {});
    capacity.assign(sink + 1, vector<int>(sink + 1, 0));
    flow.resize(sink + 1, vector<int>(sink + 1, 0));
    distanceMatrix.resize(sink + 1, vector<int>(sink + 1, 0));

    // Construirea grafului și inițializarea capacitatilor și distanțelor
    for (int i = 1; i <= N; i++) {
        graph[0].push_back(i);
        graph[i].push_back(0);
        capacity[0][i] = 1;

        for (int j = 1; j <= N; j++) {
            fin >> distanceMatrix[i][j];
            graph[i].push_back(j + N);
            graph[j + N].push_back(i);
            capacity[i][j + N] = 1;
            distanceMatrix[j + N][i] = -distanceMatrix[i][j];
        }
    }

    // Adăugarea nodurilor destinație și inițializarea capacitatilor
    for (int i = 1; i <= N; i++) {
        graph[i + N].push_back(sink);
        graph[sink].push_back(i + N);
        capacity[i + N][sink] = 1;
    }

    // Apelul algoritmului Edmonds-Karp
    edmondsKarp();

    // Scrierea rezultatului în fișierul de ieșire
    fout << totalDistance;

    return 0;
}