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.

4
0 6 62 13
6 0 35 94
62 35 0 5
13 94 5 0
0

156