该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题意简述

有一个无向图，$i$ 到 $j$ 的距离为 $D_{i,j}$。你可以选择一些边，使得这些边连接的所有顶点互不相同。求这些边总长度的最大值。

输入格式

以以下格式输入：

$N$ $D_{1,2},D_{1,3},\ldots,D_{1,N}$ $D_{2,3},\ldots,D_{2,N}$ $\vdots$ $D_{N-1,N}$

输出格式

$1$ 个整数。如题意。

提示

• $2 \le N \le 16$
• $1 \le D_{i,j} \le 10^9$

样例一解释

选择 $D_{1,3},D_{2,4}$，总和为$5+8=13$。

题目描述

頂点に $1$ から $N$ の番号が付いた $N$ 頂点の重み付き無向完全グラフが与えられます。頂点 $i$ と頂点 $j\ (i\ <\ j)$ を結ぶ辺の重みは $D_{i,j}$ です。

以下の条件を満たすように何本かの辺を選ぶとき、選んだ辺の重みの総和としてあり得る最大値を求めてください。

• 選んだ辺の端点はどの $2$ 個も相異なる。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $D_{1,2}$ $D_{1,3}$ $\ldots$ $D_{1,N}$ $D_{2,3}$ $\ldots$ $D_{2,N}$ $\vdots$ $D_{N-1,N}$

输出格式

答えを整数として出力せよ。

样例 #1

样例输入 #1

4
1 5 4
7 8
6

样例输出 #1

13

样例 #2

样例输入 #2

3
1 2
3

样例输出 #2

3

样例 #3

样例输入 #3

16
5 6 5 2 1 7 9 7 2 5 5 2 4 7 6
8 7 7 9 8 1 9 6 10 8 8 6 10 3
10 5 8 1 10 7 8 4 8 6 5 1 10
7 4 1 4 5 4 5 10 1 5 1 2
2 9 9 7 6 2 2 8 3 5 2
9 10 3 1 1 2 10 7 7 5
10 6 1 8 9 3 2 4 2
10 10 8 9 2 10 7 9
5 8 8 7 5 8 2
4 2 2 6 8 3
2 7 3 10 3
5 7 10 3
8 5 7
9 1
4

样例输出 #3

75

提示

制約

• $2\leq\ N\leq\ 16$
• $1\leq\ D_{i,j}\ \leq\ 10^9$
• 入力される数値は全て整数

Sample Explanation 1

頂点 $1$ と頂点 $3$ を結ぶ辺、頂点 $2$ と頂点 $4$ を結ぶ辺を選ぶと、辺の重みの総和が $5+8=13$ となります。 これが達成可能な最大値であることが示せます。

Sample Explanation 2

$N$ が奇数の場合もあります。