3
75 15 21 
75 15 28 
34 70 5 

188

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<set>
#include<queue>
#include<stack>
#include<vector>
#include<map>

#define N 100010
#define Mod 10000007
#define lson l,mid,idx<<1
#define rson mid+1,r,idx<<1|1
#define lc idx<<1
#define rc idx<<1|1
const double EPS = 1e-11;
const double PI = acos ( -1.0 );
const double E = 2.718281828;
typedef long long ll;

const int INF = 1000010;

using namespace std;

const int M=3030;///测了几个数据，所有情况3000种左右
int a[22][22], cnt[M], n, len;
int dp[22][M], sum[22][M];

bool ok ( int x )///判断同一行的x情况是否符合条件，即不能相邻
{
    if ( x & ( x << 1 ) ) return false;
    return true;
}

void build()///将符合条件的数存起来
{
    len = 0;
    for ( int i = 0; i < ( 1 << n ); i++ )
        if ( ok ( i ) )
            cnt[len++] = i;
}

int getsum ( int i, int x )///计算第i行，x情况时的值
{
    int sum = 0;
    int j = 0;
    while ( x > 0 )
    {
        if ( x & 1 )
            sum += a[i][j];
        x >>= 1;
        j++;
    }
    return sum;
}

void finds()///把所有的情况都算出来
{
    for ( int i = 0; i < n; i++ )
        for ( int j = 0; j < len; j++ )
            sum[i][j] = getsum ( i, cnt[j] );
}

int main()
{
    //freopen("in.txt","r",stdin);
    while ( cin >> n )
    {
        for ( int i = 0; i < n; i++ )
            for ( int j = 0; j < n; j++ )
                scanf ( "%d", &a[i][j] );
        memset ( dp, -1, sizeof dp );
        build();
        finds();
        for ( int i = 0; i < len; i++ )///先算第0行
            dp[0][i] = sum[0][i];
        for ( int i = 1; i < n; i++ )
        {
            for ( int j = 0; j < len; j++ )
            {
                int x = -1;
                for ( int k = 0; k < len; k++ )///找出符合情况的最大值
                {
                    if ( dp[i - 1][k] != -1 && ( ! ( cnt[j]&cnt[k] ) ) && dp[i - 1][k] > x )
                        x = dp[i - 1][k];
                }
                dp[i][j] = x + sum[i][j];
            }
        }
        int ans = -1;
        for ( int i = 0; i < len; i++ )
            if ( dp[n - 1][i] > ans )
                ans = dp[n - 1][i];
        cout << ans << endl;
    }
    return 0;
}