# 描述

Recently, researchers on Mars have discovered N powerful atoms. All of them are different. These atoms have some properties. When two of these atoms collide, one of them disappears and a lot of power is produced. Researchers know the way every two atoms perform when collided and the power every two atoms can produce.

You are to write a program to make it most powerful, which means that the sum of power produced during all the collides is maximal.

## Input

There are multiple cases. The first line of each case has an integer $N (2 <= N <= 10)$, which means there are N atoms: $A_1, A_2, … , A_N$. Then $N$ lines follow. There are $N$ integers in each line. The $j^{th}$ integer on the $i^{th}$ line is the power produced when $A_i$ and $A_j$ collide with $A_j$ gone. All integers are positive and not larger than 10000.

The last case is followed by a 0 in one line.

There will be no more than 500 cases including no more than 50 large cases that $N$ is 10.

## Output

Output the maximal power these $N$ atoms can produce in a line for each case.

• intput

• output

# 思路

• 状态dp入门题，用0来表示未泯灭，1表示已经泯灭，这样就能用一个n位的整数来记录所有的状态。
• 对于状态i，假设第j位和第k位都是0，那么我们就可以通过dp[i]推出 dp[i&1<<k]的状态。
• 状态转移方程：

# 代码

-------------本文结束 感谢您的阅读-------------