文理学院程序设计在线练习


最佳组队问题

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 247   Accepted Submission(s): 97
Problem Description

双人混合ACM程序设计竞赛即将开始,因为是双人混合赛,故每支队伍必须由1男1女组成。现在需要对n名男队员和n名女队员进行配对。由于不同队员之间的配合优势不一样,因此,如何组队成了大问题。
给定n×n优势矩阵P,其中P[i][j]表示男队员i和女队员j进行组队的竞赛优势(0<P[i][j]<10000)。设计一个算法,计算男女队员最佳配对法,使组合出的n支队伍的竞赛优势的总和达到最大值。

Input

每组测试数据第一行有1个正整数n(1≤n≤9)。接下来有n行,每行n个数, 分别代表优势矩阵P的各元素。处理到文件结束。

Output

输出n支队伍的竞赛优势的总和的最大值。

Sample Input
3
10 2 3
2 3 4
3 4 5
Sample Output
18