题目描述

ASD 大学的电脑网络由 \(N\) 台计算机组成，将每台计算机从 \(1\) 到 \(N\) 进行编号。网络管理员 Smart 知道任意两台计算机之间都可以通信且它们之间的通信费用。Smart 已经将整个网络划分为两个子网络，目的是使这两个子网络之间的通信费用之和最小。

小 \(Y\) 是一个不遵守学校纪律的学生，被学校开除之后为了报复学校他准备攻击学校网络，把网络中所有计算机重新分配成两个子网络，让重新分配后的两个子网络之间的通信费用之和达到最大。

由于小 \(Y\) 在大学也没有学到什么，虽然有复仇想法但无能力实施，于是想求助于更加有本事且又聪明的你来帮助他。计算机之间的通信费用是通过矩阵 \(C\) 的形式给你，\(C[i][j]\) 表示计算机 \(i\) 与计算机 \(j\) 之间的通信费用（有 \(C[i][j]=C[j][i]\)，\(C[i][i]=0\)），你的任务是把网络中的 \(N\) 台计算机划分为两个子网络 \(A\) 和 \(B\) ，使 \(∑C[i][j](i∈A,j∈B)\)最大。

格式

输入格式

第一行只有一个整数 \(N\)；
接下来 \(N\) 行，每行 \(N\) 个用空格隔开的整数 \(C[i][j]\)，表示计算机 \(i\) 与计算机 \(j\) 之间的通信费用。

输出格式

只有一个整数，即两个子网之间最大的通信费用之和。

样例1

样例输入1

3
0 50 30
50 0 40
30 40 0

样例输出1

90

限制

\(100\%\) 的数据：\(2≤N≤22，0≤C[i][j]≤10000\)。