Problem Description
Say love to you once again------I remember that day, you're sitting in front of me. Obviously your wishes, waiting for my performance. I said some other day, when I have sufficient time
, I would certainly give you a perfect declaration of love. I would like to seize every moment, I am afraid that the story is yesterday. I came to realize that neglect is the largest defect of me, but it was to late. I really want to say love to you once again. I am willing to give up everything only in exchange for you. If time can turn the clock back for you. I will hold your hands once again, say, I love you!
It is an old legend.
If you can solve this problem, god will give you a chance to say love to your darling once again, so, yifenfei, seize the chance.
There are N plane in the sky, and every one can attack each other. Now, we assigned each has a number i (1 <= i <= N), plane i and plane j can produce Aij points of hurt. Your task is to divide N planes into two groups. Each group in itself don’t produce any point of hurt, but plane between two groups will produces hurt.
Please maximize sum of all the hurt.
Input
For each case, first input a N(2 <= N <= 25), represent the number of planes in the sky, then a matrix A, (Aij = Aji, Aii = 0 for all i,j<= N), Aij represents the hurt between plane i and plane j.
Output
Output the largest hurt between two groups.
Sample Input
3
0 150 20
150 0 140
20 140 0
Sample Output
290.
