Say love to you once again

Time Limit: 6000/2000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

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.

Hint

zty

Source

醉卧沙场君莫笑

提交代码