#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 + 2;
        s = nr_noduri - 2;
        t = nr_noduri - 1;
        adiac.resize(nr_noduri);
        costs.resize(nr_noduri);
        int cost;
        for(int i = 0; i < n; i++){
            adiac[s][i] = 1;
            adiac[i][s] = 0;
            adiac[i + n][t] = 1;
            costs[s][i] = 0;
            costs[i][s] = infinity;
            costs[i + n][t] = 0;
            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;
            }
        }
    }
    int dinic(){
        int flux = 0;
        vector<int> level_graph(nr_noduri);
        while(make_level_graph(level_graph)){
            bool still_running = true;
            while(still_running) {
                still_running = false;
                int curent_flow = dfs(s, infinity, level_graph);
                if (curent_flow > 0) {
                    still_running = true;
                    flux += curent_flow;
                }
            }
        }
        return flux;
    }
    int dfs(int index, int flux, vector<int>& level){
        if(index == t)
            return flux;
        for(auto& vec : adiac[index]){
            if(level[vec.first] > level[index] && vec.second > 0){
                int fl = dfs(vec.first, min(flux, vec.second), level);
                if(fl > 0) {
                    adiac[index][vec.first] -= fl;
                    adiac[vec.first][index] += fl;
                    return fl;
                }
                else{
                    level[vec.first] = -1;
                }
            }
        }
        return 0;
    }
    bool make_level_graph(vector<int>& level){
        fill(level.begin(), level.end(), -1);
        queue<int> coada;
        coada.push(s);
        level[s] = 0;
        while(!coada.empty()){
            int curent = coada.front();
            coada.pop();
            for(auto vec : adiac[curent]){
                if(level[vec.first] == -1 && vec.second > 0){
                    level[vec.first] = level[curent] + 1;
                    coada.push(vec.first);
                }
            }
        }
        return (level[t] != -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.dinic();
    graf.cancel_negative_cycles();
    g << graf.used_edges_cost();
    return 0;
}