问题描述

给定一个加权无向完全图，图中有 N 个顶点，编号从 1 到 N。连接顶点 i 和 j（其中 i < j）的边的权重为 D_i,j。

在以下条件下，选择若干条边，找到选定边的权重之和的最大值：

• 选定的边的端点要两两不同。

输入格式

输入的格式如下：

• 第一行输入一个整数 N，表示顶点的数量。
• 接下来的 N*(N-1)/2 行，每行输入两个整数 D_i,j，表示连接顶点 i 和顶点 j（其中 i < j）的边的权重。

输出格式

输出一个整数，表示选定边的最大权重和。

输入约束

• 2 ≤ N ≤ 16
• 1 ≤ D_i,j ≤ 10^9
• 所有输入值均为整数。

示例输入 1

4
1 5 4
7 8
6

示例输出 1

13

​解释​： 如果选择连接顶点 1 和顶点 3 的边，以及连接顶点 2 和顶点 4 的边，则这些边的权重和为 5 + 8 = 13。这是最大可以达到的总权重。

示例输入 2

3
1 2
3

示例输出 2

3

​解释​： 在 N=3 的情况下，选择边 (1, 2) 或 (1, 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