HUST 2016招新选拔

From: 2016-03-06 14:00:00 To: 2016-03-06 17:30:00 Now: 2017-09-24 21:44:18 Status: Public

I - Work Together

Time Limit: 1s Memory Limit: 512MB

Submissions: 24 Solved: 9
Description

Thulium’s father is running a small company now with N employees. The numbers of employees are from 1 to N. There are N/2 groups now. Each group has a project. One employee only can be in one group. Give you Pij means people i and people j work together can make Pij profit. Given all the Pij, figure out the most profits you can make. 

Input

The first line is N (2<=N<=10 and N is an even number). 

Then has N lines and each line has n numbers.

That represents Pij(1 <= i <= N,1 <= j <= N,0 < Pij<= 100).

The end 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
Hint
Source