Time Limit : 1 Second
Memory Limit : 512 MB
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.
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.
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