Partition problem
题号:NC50895
时间限制:C/C++/Rust/Pascal 4秒,其他语言8秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

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 

输入描述:

The first line of input contains an integers N.

Following 2N lines each contains 2N space-separated integers  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

输出

复制
3