题目描述

Given 2N people, you need to assign each of them into either red team or white team such that each team consists of exactly N people and the total competitive value is maximized.

Total competitive value is the summation of competitive value of each pair of people in different team.

The equivalent equation is $\sum_{i=1}^{2N} \sum_{j=i+1}^{2N} (v_{ij} \text{ if i-th person is not in the same team as j-th person else } 0 )$

输入格式

The first line of input contains an integers N.

Following 2N lines each contains 2N space-separated integers $v_{ij}$ is the j-th value of the i-th line which indicates the competitive value of person i and person j.

输出格式

Output one line containing an integer representing the maximum possible total competitive value.

样例

样例输入 1

1
0 3
3 0

样例输出 1

3

数据范围与提示

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