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

using namespace std;

ifstream inputFile("cc.in");    // Fluxul de intrare din fișierul "cc.in"
ofstream outputFile("cc.out");  // Fluxul de ieșire în fișierul "cc.out"

int numNodes, sourceNode, targetNode, distance;
vector<vector<int>> adjacencyList, capacity, flow, distanceMatrix;
vector<int> previousNode, minDistance;
int result;

// Funcție pentru inițializarea nodurilor precedente și a distanței minime
void initializePreviousNodes() {
    for (int i = 0; i <= targetNode; i++) {
        previousNode[i] = -1;
        minDistance[i] = INT_MAX;
    }
    minDistance[0] = 0;
}

// Funcție pentru parcurgerea în lățime (BFS) pentru găsirea unui drum de la sursă la destinație
int bfs() {
    initializePreviousNodes();
    queue<pair<int, int>> q;
    q.push({0, INT_MAX});

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

        for (auto &next : adjacencyList[current]) {
            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[targetNode] >= 0;
}

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

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

        int current = targetNode;
        // 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ă
        result += minDistance[targetNode];
    }
    outputFile << result;
}

int main() {
    inputFile >> numNodes;
    targetNode = 2 * numNodes + 1;
    previousNode.resize(targetNode + 1);
    minDistance.resize(targetNode + 1);
    adjacencyList.resize(targetNode + 1, {});

    // Inițializarea matricelor de capacitate, flux și distanță
    capacity.assign(targetNode + 1, vector<int>(targetNode + 1, 0));
    flow.resize(targetNode + 1, vector<int>(targetNode + 1, 0));
    distanceMatrix.resize(targetNode + 1, vector<int>(targetNode + 1, 0));

    for (int i = 1; i <= numNodes; i++) {
        adjacencyList[0].push_back(i);
        adjacencyList[i].push_back(0);
        capacity[0][i] = 1;

        for (int j = 1; j <= numNodes; j++) {
            inputFile >> distance;

            // Adăugarea nodurilor și inițializarea matricii de distanțe
            adjacencyList[i].push_back(j + numNodes);
            adjacencyList[j + numNodes].push_back(i);
            capacity[i][j + numNodes] = 1;
            distanceMatrix[i][j + numNodes] = distance;
            distanceMatrix[j + numNodes][i] = -distance;
        }
    }

    for (int i = 1; i <= numNodes; i++) {
        adjacencyList[i + numNodes].push_back(targetNode);
        adjacencyList[targetNode].push_back(i + numNodes);
        capacity[i + numNodes][targetNode] = 1;
    }

    edmondsKarpAlgorithm();

    return 0;
}