# 計算量O(n^3)
#  NetworkX の max_wieght_matching() のソースをもとに改変。
#  元のソースコードに対し、以下の変更を加えた。
#  ・入力するグラフ G は、NetworkXの Graph オブジェクトでなく、下記で定義した簡易版のGraphオブジェクト
#  ・返り値は、マッチングのペアを表す辞書 mate でなく、マッチングした辺の合計の最大値 max_weight に変更。
#  ・コメントの削除
#  ・maxcardinality = True にデフォルトを変更。
#  ・検算用の関数 および assert文を削除。
#
#  以下のコピーライト表記は、元のソースコードのもの。
#    Copyright (C) 2004-2015 by
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>
#    All rights reserved.
#    BSD license.
#   Copyright (C) 2011 by
#   Nicholas Mancuso <nick.mancuso@gmail.com>
#   All rights reserved.
#   BSD license.
from itertools import repeat

class Graph(object):
    '''重み付き無向グラフを表すクラス。 max_weight_matching() の入力に使うためのラッパーで、networkXのグラフクラスを模倣する。
    G.nodes() : ノードのリストを返す。
    G.edges_iter(data=True): (i, j, data)のタプルを順にyieldする。i, j は辺の両端の頂点。dataは、辺に関連付けられたデータ（辞書）。
    data.get("weight") で辺の重みを取得できる。 -> 回りくどいので、dataを辞書ではなく、重みを表すintとした。
    G[i][j]: 辺(i, j)に関連付けられたデータを返す。->回りくどいので、dataを返すのでなく、重みを表すintを返すとした。
    G.neighbors_iter(v): 頂点 v に隣接する頂点を順にyieldする。
    '''
    def __init__(self, Es):
        ''' Es: Es[v] に、頂点vの辺の一覧の辞書（隣接頂点をキー、辺の重みを値）を格納したリスト
        頂点は、0 から、len(Es)-1 までの整数連番で表す。
        '''
        self.Vs = list(range(len(Es)))
        self.Es = Es
        self._init_edges()
    
    def nodes(self):
        return self.Vs[:]
    
    def neighbors_iter(self, v):
        return self.Es[v].keys()

    def edges_iter(self, data=True):
        if data:
            return iter(self.edges_with_weight)
        else:
            return iter(self.edges)
    
    def __getitem__(self, v):
        return self.Es[v]
    
    def _init_edges(self):
        edges = set()
        for v in self.Vs:
            for u, w in self.Es[v].items():
                edges.add((min(v, u), max(v, u), w))
        self.edges_with_weight = list(edges)
        self.edges = [(u, v) for u, v, w in self.edges_with_weight]
        

def max_weight_matching(G, maxcardinality=True):
    """Compute a maximum-weighted matching of G.

    A matching is a subset of edges in which no node occurs more than once.
    The cardinality of a matching is the number of matched edges.
    The weight of a matching is the sum of the weights of its edges.

    Parameters
    ----------
    G : NetworkX graph
      Undirected graph

    maxcardinality: bool, optional
       If maxcardinality is True, compute the maximum-cardinality matching
       with maximum weight among all maximum-cardinality matchings.

    Returns
    -------
    mate : dictionary -> max_weight : int を返す仕様に変更。
       The matching is returned as a dictionary, mate, such that
       mate[v] == w if node v is matched to node w.  Unmatched nodes do not
       occur as a key in mate.


    Notes
    -----
    If G has edges with 'weight' attribute the edge data are used as
    weight values else the weights are assumed to be 1.

    This function takes time O(number_of_nodes ** 3).

    If all edge weights are integers, the algorithm uses only integer
    computations.  If floating point weights are used, the algorithm
    could return a slightly suboptimal matching due to numeric
    precision errors.

    This method is based on the "blossom" method for finding augmenting
    paths and the "primal-dual" method for finding a matching of maximum
    weight, both methods invented by Jack Edmonds [1]_.

    Bipartite graphs can also be matched using the functions present in
    :mod:`networkx.algorithms.bipartite.matching`.

    References
    ----------
    .. [1] "Efficient Algorithms for Finding Maximum Matching in Graphs",
       Zvi Galil, ACM Computing Surveys, 1986.
    """
    #
    # The algorithm is taken from "Efficient Algorithms for Finding Maximum
    # Matching in Graphs" by Zvi Galil, ACM Computing Surveys, 1986.
    # It is based on the "blossom" method for finding augmenting paths and
    # the "primal-dual" method for finding a matching of maximum weight, both
    # methods invented by Jack Edmonds.
    #
    # A C program for maximum weight matching by Ed Rothberg was used
    # extensively to validate this new code.
    #
    # Many terms used in the code comments are explained in the paper
    # by Galil. You will probably need the paper to make sense of this code.
    #

    class NoNode:
        pass

    class Blossom:
        __slots__ = [ 'childs', 'edges', 'mybestedges' ]
        def leaves(self):
            for t in self.childs:
                if isinstance(t, Blossom):
                    for v in t.leaves():
                        yield v
                else:
                    yield t

    gnodes = G.nodes()

    maxweight = 0
    allinteger = True
    for i,j,wt in G.edges_iter(data=True):
        if i != j and wt > maxweight:
            maxweight = wt

    mate = { }
    label = { }
    labeledge = { }
    inblossom = dict(zip(gnodes, gnodes))
    blossomparent = dict(zip(gnodes, repeat(None)))
    blossombase = dict(zip(gnodes, gnodes))
    bestedge = { }
    dualvar = dict(zip(gnodes, repeat(maxweight)))
    blossomdual = { }
    allowedge = { }
    queue = [ ]

    def slack(v, w):
        return dualvar[v] + dualvar[w] - 2 * G[v][w]

    def assignLabel(w, t, v):
        b = inblossom[w]
        label[w] = label[b] = t
        if v is not None:
            labeledge[w] = labeledge[b] = (v, w)
        else:
            labeledge[w] = labeledge[b] = None
        bestedge[w] = bestedge[b] = None
        if t == 1:
            if isinstance(b, Blossom):
                queue.extend(b.leaves())
            else:
                queue.append(b)
        elif t == 2:
            base = blossombase[b]
            assignLabel(mate[base], 1, base)

    def scanBlossom(v, w):
        path = [ ]
        base = NoNode
        while v is not NoNode:
            b = inblossom[v]
            if label[b] & 4:
                base = blossombase[b]
                break
            path.append(b)
            label[b] = 5
            if labeledge[b] is None:
                v = NoNode
            else:
                v = labeledge[b][0]
                b = inblossom[v]
                v = labeledge[b][0]
            if w is not NoNode:
                v, w = w, v
        for b in path:
            label[b] = 1
        return base

    def addBlossom(base, v, w):
        bb = inblossom[base]
        bv = inblossom[v]
        bw = inblossom[w]
        b = Blossom()
        blossombase[b] = base
        blossomparent[b] = None
        blossomparent[bb] = b
        b.childs = path = [ ]
        b.edges  = edgs = [ (v, w) ]
        while bv != bb:
            blossomparent[bv] = b
            path.append(bv)
            edgs.append(labeledge[bv])
            v = labeledge[bv][0]
            bv = inblossom[v]
        path.append(bb)
        path.reverse()
        edgs.reverse()
        while bw != bb:
            blossomparent[bw] = b
            path.append(bw)
            edgs.append((labeledge[bw][1], labeledge[bw][0]))
            w = labeledge[bw][0]
            bw = inblossom[w]
        label[b] = 1
        labeledge[b] = labeledge[bb]
        blossomdual[b] = 0
        for v in b.leaves():
            if label[inblossom[v]] == 2:
                queue.append(v)
            inblossom[v] = b
        bestedgeto = { }
        for bv in path:
            if isinstance(bv, Blossom):
                if bv.mybestedges is not None:
                    nblist = bv.mybestedges
                    bv.mybestedges = None
                else:
                    nblist = [ (v, w)
                                for v in bv.leaves()
                                for w in G.neighbors_iter(v)
                                if v != w ]
            else:
                nblist = [ (bv, w)
                           for w in G.neighbors_iter(bv)
                           if bv != w ]
            for k in nblist:
                (i, j) = k
                if inblossom[j] == b:
                    i, j = j, i
                bj = inblossom[j]
                if (bj != b and label.get(bj) == 1 and
                    ((bj not in bestedgeto) or
                     slack(i, j) < slack(*bestedgeto[bj]))):
                    bestedgeto[bj] = k
            bestedge[bv] = None
        b.mybestedges = list(bestedgeto.values())
        mybestedge = None
        bestedge[b] = None
        for k in b.mybestedges:
            kslack = slack(*k)
            if mybestedge is None or kslack < mybestslack:
                mybestedge = k
                mybestslack = kslack
        bestedge[b] = mybestedge

    def expandBlossom(b, endstage):
        for s in b.childs:
            blossomparent[s] = None
            if isinstance(s, Blossom):
                if endstage and blossomdual[s] == 0:
                    expandBlossom(s, endstage)
                else:
                    for v in s.leaves():
                        inblossom[v] = s
            else:
                inblossom[s] = s
        if (not endstage) and label.get(b) == 2:
            entrychild = inblossom[labeledge[b][1]]
            j = b.childs.index(entrychild)
            if j & 1:
                j -= len(b.childs)
                jstep = 1
            else:
                jstep = -1
            v, w = labeledge[b]
            while j != 0:
                if jstep == 1:
                    p, q  = b.edges[j]
                else:
                    q, p = b.edges[j-1]
                label[w] = None
                label[q] = None
                assignLabel(w, 2, v)
                allowedge[(p, q)] = allowedge[(q, p)] = True
                j += jstep
                if jstep == 1:
                    v, w = b.edges[j]
                else:
                    w, v = b.edges[j-1]
                allowedge[(v, w)] = allowedge[(w, v)] = True
                j += jstep
            bw = b.childs[j]
            label[w] = label[bw] = 2
            labeledge[w] = labeledge[bw] = (v, w)
            bestedge[bw] = None
            j += jstep
            while b.childs[j] != entrychild:
                bv = b.childs[j]
                if label.get(bv) == 1:
                    j += jstep
                    continue
                if isinstance(bv, Blossom):
                    for v in bv.leaves():
                        if label.get(v):
                            break
                else:
                    v = bv
                if label.get(v):
                    label[v] = None
                    label[mate[blossombase[bv]]] = None
                    assignLabel(v, 2, labeledge[v][0])
                j += jstep
        label.pop(b, None)
        labeledge.pop(b, None)
        bestedge.pop(b, None)
        del blossomparent[b]
        del blossombase[b]
        del blossomdual[b]

    def augmentBlossom(b, v):
        t = v
        while blossomparent[t] != b:
            t = blossomparent[t]
        if isinstance(t, Blossom):
            augmentBlossom(t, v)
        i = j = b.childs.index(t)
        if i & 1:
            j -= len(b.childs)
            jstep = 1
        else:
            jstep = -1
        while j != 0:
            j += jstep
            t = b.childs[j]
            if jstep == 1:
                w, x = b.edges[j]
            else:
                x, w = b.edges[j-1]
            if isinstance(t, Blossom):
                augmentBlossom(t, w)
            j += jstep
            t = b.childs[j]
            if isinstance(t, Blossom):
                augmentBlossom(t, x)
            mate[w] = x
            mate[x] = w
        b.childs = b.childs[i:] + b.childs[:i]
        b.edges  = b.edges[i:]  + b.edges[:i]
        blossombase[b] = blossombase[b.childs[0]]
        assert blossombase[b] == v

    def augmentMatching(v, w):
        for (s, j) in ((v, w), (w, v)):
            while 1:
                bs = inblossom[s]
                if isinstance(bs, Blossom):
                    augmentBlossom(bs, s)
                mate[s] = j
                if labeledge[bs] is None:
                    break
                t = labeledge[bs][0]
                bt = inblossom[t]
                s, j = labeledge[bt]
                if isinstance(bt, Blossom):
                    augmentBlossom(bt, j)
                mate[j] = s

    while 1:
        label.clear()
        labeledge.clear()
        bestedge.clear()
        for b in blossomdual:
            b.mybestedges = None
        allowedge.clear()
        queue[:] = [ ]
        for v in gnodes:
            if (v not in mate) and label.get(inblossom[v]) is None:
                assignLabel(v, 1, None)
        augmented = 0
        while 1:
            while queue and not augmented:
                v = queue.pop()
                assert label[inblossom[v]] == 1
                for w in G.neighbors_iter(v):
                    if w == v:
                        continue # ignore self-loops
                    bv = inblossom[v]
                    bw = inblossom[w]
                    if bv == bw:
                        continue
                    if (v, w) not in allowedge:
                        kslack = slack(v, w)
                        if kslack <= 0:
                            allowedge[(v, w)] = allowedge[(w, v)] = True
                    if (v, w) in allowedge:
                        if label.get(bw) is None:
                            assignLabel(w, 2, v)
                        elif label.get(bw) == 1:
                            base = scanBlossom(v, w)
                            if base is not NoNode:
                                addBlossom(base, v, w)
                            else:
                                augmentMatching(v, w)
                                augmented = 1
                                break
                        elif label.get(w) is None:
                            label[w] = 2
                            labeledge[w] = (v, w)
                    elif label.get(bw) == 1:
                        if bestedge.get(bv) is None or kslack < slack(*bestedge[bv]):
                            bestedge[bv] = (v, w)
                    elif label.get(w) is None:
                        if bestedge.get(w) is None or kslack < slack(*bestedge[w]):
                            bestedge[w] = (v, w)
            if augmented:
                break
            deltatype = -1
            delta = deltaedge = deltablossom = None
            if not maxcardinality:
                deltatype = 1
                delta = min(dualvar.values())
            for v in gnodes:
                if label.get(inblossom[v]) is None and bestedge.get(v) is not None:
                    d = slack(*bestedge[v])
                    if deltatype == -1 or d < delta:
                        delta = d
                        deltatype = 2
                        deltaedge = bestedge[v]
            for b in blossomparent:
                if ( blossomparent[b] is None and label.get(b) == 1 and
                     bestedge.get(b) is not None ):
                    kslack = slack(*bestedge[b])
                    if allinteger:
                        d = kslack // 2
                    else:
                        d = kslack / 2.0
                    if deltatype == -1 or d < delta:
                        delta = d
                        deltatype = 3
                        deltaedge = bestedge[b]
            for b in blossomdual:
                if ( blossomparent[b] is None and label.get(b) == 2 and
                     (deltatype == -1 or blossomdual[b] < delta) ):
                    delta = blossomdual[b]
                    deltatype = 4
                    deltablossom = b
            if deltatype == -1:
                deltatype = 1
                delta = max(0, min(dualvar.values()))
            for v in gnodes:
                if label.get(inblossom[v]) == 1:
                    dualvar[v] -= delta
                elif label.get(inblossom[v]) == 2:
                    dualvar[v] += delta
            for b in blossomdual:
                if blossomparent[b] is None:
                    if label.get(b) == 1:
                        blossomdual[b] += delta
                    elif label.get(b) == 2:
                        blossomdual[b] -= delta
            if deltatype == 1:
                break
            elif deltatype == 2:
                (v, w) = deltaedge
                allowedge[(v, w)] = allowedge[(w, v)] = True
                queue.append(v)
            elif deltatype == 3:
                (v, w) = deltaedge
                allowedge[(v, w)] = allowedge[(w, v)] = True
                queue.append(v)
            elif deltatype == 4:
                expandBlossom(deltablossom, False)
        if not augmented:
            break
        for b in list(blossomdual.keys()):
            if b not in blossomdual:
                continue # already expanded
            if ( blossomparent[b] is None and label.get(b) == 1 and
                 blossomdual[b] == 0 ):
                expandBlossom(b, True)

    max_weight = sum(G[u][v] for u, v in mate.items())//2
    return max_weight

def read_data():
    n = int(input())
    F = [list(map(int, input().split())) for _ in range(n)]
    return n, F

def solve(n, F):
    Es = [dict() for _ in range(n)]
    for u, f in enumerate(F):
        for v, w in enumerate(f):
            if v == u:continue
            Es[u][v] = w
    G = Graph(Es)
    return max_weight_matching(G)

n, F = read_data()
print(solve(n, F))