问题

输入将以类似邻接矩阵的形式给出一个顶点为 \(1\) 至 \(n\) 的加权无向完全图，矩阵中的数即为边的权重。准确地说：

• 第 \(1\) 行输入一个数 \(n\) 。
• 第 \(2\) 行至第 \(n+1\) 行，每行都有 \(n\) 个数。对于第 \(i\) 行（ \(2 \le i \le n+1\) ），这 \(n\) 个数分别为 \(w(i-1, 1), w(i-1, 2), \ldots, w(i-1, n)\) 。

在这里， \(w(i, j)\) 表示 \(i\) 和 \(j\) 这两个顶点所连边的权重。当然，它满足：

• \(w(i, j) = w(j, i)\) ；
• \(w(i, i) = 0\) 。

对于顶点集 \(V = \{1, 2, 3, \ldots, n\}\) ，我们可以将其划分为两部分 \(A\) 和 \(B\) 。也就是说：

• \(A \cap B = \varnothing\) ；
• \(A \cup B = V\) 。

显然，满足上述条件的划分一般不止一种。请输出下式的最大值：

\[ \sum_{a \in A} \sum_{b \in B} w(a, b) \]

但无需输出具体的划分策略。

示例

输入：

3
0 4 2
4 0 3
2 3 0

输出：

7

数据范围

• \(1 \le n \le 18\)
• \(0 \le w(i, j) \le 1000\) ，对于 \(1 \le i \le n\) 及 \(1 \le j \le n\) 。