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

using namespace std;

ifstream f("cc.in");
ofstream g("cc.out");

class Graph{
    int n, nr_noduri, s, t;
    int infinity = 1e8;
    vector<unordered_map<int, int>> adiac;
    vector<unordered_map<int, int>> costs;
public:
    Graph(){
        f >> n;
        nr_noduri = 2 * n;
        adiac.resize(nr_noduri);
        costs.resize(nr_noduri);
        int cost;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                f >> cost;
                adiac[i][j + n] = 1;
                adiac[j + n][i] = 0;
                costs[i][j + n] = cost;
                costs[j + n][i] = -cost;
            }
        }
    }
    void bad_matching(){
        for(int i = 0; i < n; i++) {
            adiac[i][i + n] = 0;
            adiac[i + n][i] = 1;
        }
    }
    void cancel_negative_cycles(){
        vector<int> parent(nr_noduri);
        int nod = bellman_ford(parent);
        while(nod != -1) {
            if (nod == -1)
                return;
            vector<bool> visited(nr_noduri, false);
            while (!visited[nod]) {
                visited[nod] = true;
                nod = parent[nod];
            }
            //Am dat de un nod in ciclu
            int stop = nod;
            nod = parent[nod];
            while (nod != stop) {
                adiac[nod][parent[nod]]++;
                adiac[parent[nod]][nod]--;
                nod = parent[nod];
            }
            adiac[nod][parent[nod]]++;
            adiac[parent[nod]][nod]--;
        nod = bellman_ford(parent);
        }
    }
    int used_edges_cost(){
       int s = 0;
//       cout << "\n Used edges: \n";
       for(int i = 0; i < n; i++)
           for(int j = 0; j < n; j++)
               if(adiac[i][j + n] == 0) {
//                   cout << "(" << i + 1<< ", " << j + 1 << ")\n";
                   s += costs[i][j + n];
               }
       return s;
    }
    int bellman_ford(vector<int>& parent){
        //Returns starting vertice for negative cycle or -1 if no such cycle exists
        //Also changes parent vector according to bellman ford relaxations
        fill(parent.begin(), parent.end(), -1);
        int curent, relaxations = 0, updated_nodes = 1;
        vector<int> dist(nr_noduri, infinity);
        queue<int> coada;
        coada.push(0);
        dist[0] = 0;
        while(!coada.empty()){
            vector<bool> in_queue(nr_noduri, false);
            int u = 0;
            vector<int> new_dist = dist;
            while(updated_nodes > 0){
                updated_nodes--;
                curent = coada.front();
                coada.pop();
                for(auto& v : adiac[curent]) {
                    if (v.second > 0) {
                        if (new_dist[v.first] > dist[curent] + costs[curent][v.first]) {
                            new_dist[v.first] = min(new_dist[v.first], dist[curent] + costs[curent][v.first]);
                            parent[v.first] = curent;
                            if (!in_queue[v.first]) {
                                u++;
                                coada.push(v.first);
                                in_queue[v.first] = true;
                            }
                        }
                    }
                }
            }
            if(u > 0) {
                updated_nodes = u;
                dist = new_dist;
                relaxations++;
            }
            if(relaxations == nr_noduri)
                return curent;
        }
        return -1;
    }
};
int main() {
    Graph graf;
    graf.bad_matching();
    graf.cancel_negative_cycles();
    g << graf.used_edges_cost();
    return 0;
}