K.Teamwork Brings Profits!
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 19 Accepted Submission(s) : 17
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
Williammed's father is running a small company now, which has N employees.(2<=N<=10 and N is an even number). The employees are numbered from 1 to N. All the employees are divided into N/2 groups. One employee can only be in one group, and each group works on one project. As we all know, teamwork is very important to a company, so different team can make different profits. And now, given any two people i and j, Williammed's father can tell how much profit(Pij) can they make if they work together. Here comes the problem, given all the Pij(1 <= i <= N,1 <= j <= N,0 < Pij<= 100), you should tell the most profits this company can make. This is an easy problem, isn't it?
Input
The first line of the input is N(2<=N<=10 and N is an even number),the number of employees in the company.
Then there're N lines,each line has N numbers.The jth number in the ith line is Pij,as we discribe above.And we guarantee Pij = Pji,Pii = 0.
The end-of-file is denoted by a single line containing the integer 0.
Then there're N lines,each line has N numbers.The jth number in the ith line is Pij,as we discribe above.And we guarantee Pij = Pji,Pii = 0.
The end-of-file is denoted by a single line containing the integer 0.
Output
For each case,output the most profits this company can make.
Sample Input
4 0 6 62 13 6 0 35 94 62 35 0 5 13 94 5 0 0
Sample Output
156
Author
Source
Developing School's Contest 6