'''
用最大流算法求二分图的最大花费最大匹配和最小花费最大匹配
工作和员工分别当做二分图中的Par1和Part2, 两个部分之间
节点的边的容量是1，费用是员工做工作的收益值，按照二分图
匹配对应的最大流模型建图即可
'''

from collections import deque

class SPFA:

    # 包含节点为1, 2, 3, 4, ..... max_node_num
    def __init__(self, start_node, edges, max_node_num):
        self.edges = edges[::]
        self.start_node = start_node
        self.max_node_num = max_node_num
        self.link = {}
        for a, b, w, idx in edges:
            if a not in self.link:
                self.link[a] = []
            self.link[a].append((b, w, idx))

    # 获取最短路径长度的列表[(节点1，长度1), (节点2, 长度2) .....]
    def getMinPathLen(self, pre, f):
        return self.getInfo(pre, f, min_path=True)

    # 获取最长路径长度列表[(节点1，长度1), (节点2, 长度2) .....]
    def getMaxPathLen(self, pre, f):
        return self.getInfo(pre, f, min_path=False)

    # min_path表示求的是最短路径还是最长路径
    def getInfo(self, pre, f, min_path = True):
        link = self.link
        dis = [0x7fffffff] * (self.max_node_num+1) if min_path else [-0x7fffffff] * (self.max_node_num+1)
        dis[self.start_node] = 0

        updated_nodes = deque()
        updated_nodes.append(self.start_node)
        in_que = [0] * (self.max_node_num + 1)
        in_que[self.start_node] = 1

        for _ in range(self.max_node_num-1):
            update_flag = False

            # 利用上一轮迭代距离变小的点进行松弛操作
            node_num = len(updated_nodes)
            for _ in range(node_num):
                a = updated_nodes.popleft()
                in_que[a] = 0
                if a not in link:
                    continue

                for b, w, edge_idx in link[a]:
                    if f[edge_idx] == 0:
                        continue

                    if dis[a] == 0x7fffffff:
                        if w == -0x7fffffff:
                            new_dis = 0
                        else:
                            new_dis = 0x7fffffff

                    elif dis[a] == -0x7fffffff:
                        if w == 0x7fffffff:
                            new_dis = 0
                        else:
                            new_dis = -0x7fffffff
                    else:
                        new_dis = dis[a] + w


                    if (min_path == True and new_dis < dis[b]) or (min_path == False and new_dis > dis[b]):
                        dis[b] = new_dis
                        pre[b] = (a, edge_idx)
                        update_flag = True

                        if in_que[b] == 0:
                            in_que[b] = 1
                            updated_nodes.append(b)

            if not update_flag:
                break

        return None


class FordFulkerson:
    # 输入图中所有边列表[(from1, to1, weight1, cost1), (form2, to2, weight2, cost1), ......]
    # weight是边的容量，cost是边的费用
    # 边可以有重边和自环边
    # souece_node 和 end_node 分别为源点和汇点
    # 所有节点从1开始连续编号, max_node_num是最大节点数，max_edge_nums是最大边数
    def __init__(self, edges, source_node, end_node, max_node_num, max_edge_num):
        self.edges = edges[::]
        self.source_node = source_node
        self.end_node = end_node
        self.max_edge_num = max_edge_num
        self.max_node_num = max_node_num

    # 费用流计算函数，min_cost为True时候获取最小费用最大流，反之获取最大费用最大流
    # 返回(最大流数值，费用值，[(from1, to1, flow1, capacity1, cost1), (from2, to2, flow2, capacity2, cost2) ......])
    # 流量方案以类表方式返回，五元组依次是边起点，边终点，边上走过的流量，原边容量，原边费用
    def getCostFlow(self, min_cost = True):
        e = [-1] * (self.max_edge_num * 2 + 1)      # e[idx]表示编号为idx残量图边的终点, idx//2 就是残量图边对应的原图边的编号
        f = [-1] * (self.max_edge_num * 2 + 1)      # f[idx]表示编号为idx的残量图边的流量
        c = [-1] * (self.max_edge_num * 2 + 1)      # c[idx]表示编号为idx的残量图的边的费用值
        ne = [-1] * (self.max_edge_num * 2 + 1)     # ne[idx]表示根编号为idx的边同一个起点的下一条边的编号
        h = [-1] * (self.max_node_num + 1)          # h[a]表示节点a为起点的所有边的链表头对应的边的编号
        orig_flow = [0] * (self.max_edge_num + 1)   # 原图中有向边的流量

        # 构建残量图
        idx = 0
        for a, b, w, cost in self.edges:
            e[idx], f[idx], c[idx], ne[idx], h[a] = b, w, cost, h[a], idx
            idx += 1
            e[idx], f[idx], c[idx], ne[idx], h[b] = a, 0, -cost, h[b], idx
            idx += 1

        max_flow_val, cost_val = 0, 0
        e1 = [(a, b, c, idx * 2) for idx, (a, b, _, c) in enumerate(self.edges)]
        e2 = [(b, a, -c, idx * 2 + 1) for idx, (a, b, _, c) in enumerate(self.edges)]
        e = e1 + e2
        algo = SPFA(self.source_node, e, self.max_node_num)

        while True:
            pre = [(None, None)] * (self.max_node_num + 1)
            if min_cost:
                algo.getMinPathLen(pre, f)
            else:
                algo.getMaxPathLen(pre, f)

            if pre[self.end_node][0] is None:
                break

            min_w = 0x7fffffff
            path_len = 0
            cur, edge_idx, next = self.end_node, 0, None
            while cur is not None:
                if next:
                    min_w = min(min_w, f[edge_idx])
                    path_len += c[edge_idx]
                cur, edge_idx, next = pre[cur][0], pre[cur][1], cur

            max_flow_val += min_w
            cost_val += path_len * min_w  # 累加费用

            cur, edge_idx, next = self.end_node, 0, None
            while cur is not None:
                if next:
                    f[edge_idx], f[edge_idx ^ 1] = f[edge_idx] - min_w, f[edge_idx ^ 1] + min_w

                    # 更新原图边的流量
                    if idx & 1:
                        orig_flow[edge_idx >> 1] -= min_w
                    else:
                        orig_flow[edge_idx >> 1] += min_w

                cur, edge_idx, next = pre[cur][0], pre[cur][1], cur

        return max_flow_val, cost_val, [(self.edges[i][0], self.edges[i][1], orig_flow[i], self.edges[i][2], self.edges[i][3]) for i in range(len(self.edges))]




n = int(input())
edges = []
for i in range(1, n+1):
    arr = list(map(int, input().split()))
    for j in range(1, n+1):
        edges.append((i, j+n, 1, arr[j-1]))

S, T = 2*n+1, 2*n+2
for node in range(1, n+1):
    edges.append((S, node, 1, 0))
for node in range(n+1, 2*n+1):
    edges.append((node, T, 1, 0))

algo = FordFulkerson(edges, S, T, 2*n+2, len(edges))
print(algo.getCostFlow()[1])
print(algo.getCostFlow(min_cost=False)[1])