题目描述

班级举行棒球比赛，给定 $2N$ 人，你需要把这些人分成成两只人数相同的队伍，来让比赛的精彩程度最大化。

其中精彩程度是两支队伍中每对人的冲突值的总和。

等价方程为 $\sum_{i=1}^{2N} \sum_{j=i+1}^{2N} v_{ij}$

第 $i$ 人与第 $j$ 人不在同一小组，否则 冲突值计算为 $0$。

输入描述

第一行输入包含一个整数 N。

随后的 $2N$ 每行分别包含 $2N$ 个空格分隔的整数 $v_{ij}$是第 $i$ 行的第 $j$ 个值，表示第 $i$ 人和第 $j$ 人的冲突值。

* $1 \leq N \leq 14$ * $0 \leq v_{ij} \leq 10^{9}$ * $v_{ij} = v_{ji}$

输出描述

输出一行，其中包含一个整数，代表可能的最大精彩程度。

样例

样例输入#1

1
0 3
3 0

样例输出#1

3