本题状压dp的简单应用，用0表示还没有消失或没有被使用的气体，1表示已经使用的气体。
每次枚举寻找两个气体，饭后将其中一个变成1就行。 
//在这里我们直接使用一维状态的转移，这样在转移的过程中去挑选值为0的两个节点
//那么这两个节点肯定有一个留下来，我们假设删除的节点为j，那么就有
//dp[state|(1<<(j-1))] = max(dp[state] + a[i][j]);
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 20;
int dp[1<<10];
int a[maxn][maxn];

signed main()
{
    int n;
    cin>>n;
    while (n)
    {
        memset(dp, 0, sizeof(dp));
        memset(a, 0, sizeof(a));
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=n;j++)
            {
                cin>>a[i][j];
            }
        }
        int len = (1<<n)-1;
        int ans = 0;
        for (int state=0;state<len;state++)
        {
            for (int i=1;i<=n;i++)
            {
                if (((state>>(i-1))&1)==1) continue;
                for (int j=1;j<=n;j++)
                {
                    if (((state>>(j-1))&1)==1) continue;
                    if (i==j) continue;
                    dp[state|(1<<(j-1))] = max(dp[state|(1<<(j-1))], dp[state]+a[i][j]);
                    ans = max(dp[state|(1<<(j-1))], ans);
//                     cout<<(state|(1<<(j-1)))<<' '<<dp[state|(1<<(j-1))]<<endl;
                }
            }
        }
        cout<<ans<<endl;
//         cout<<"---------"<<endl;
        cin>>n;
    }
    
    
    return 0;
}