#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#define N 1010

#define M 50010

#define inf 1<<30

using namespace std;

struct Edge{

    int to,val,next;

}edge[M];

int index[N],d[N],gap[N],e;

void addedge(int from,int to,int val)

{

    edge[e].to=to;

    edge[e].val=val;

    edge[e].next=index[from];

    index[from]=e++;

    edge[e].to=from;

    edge[e].val=;

    edge[e].next=index[to];

    index[to]=e++;

}

int source,des,n,m;

//n is the number of point

int dfs(int pos,int flow)

{

    if(pos==des)

        return flow;

    int i,j,v,val,lv,mind,c;

    mind=n-;//初始最小标号为n-1

    lv=flow;

    for(i=index[pos];i!=-;i=edge[i].next)

    {

        v=edge[i].to;

        val=edge[i].val;

        if(val)

        {

            if(d[v]+==d[pos])

            {

                c=min(lv,val);//对于该点的最小可行流

                c=dfs(v,c);

                edge[i].val-=c;//更新剩余图

                edge[i^].val+=c;

                lv-=c;

                if(d[source]>=n)return flow-lv;

                if(lv==) break;

            }

            if(d[v]<mind)mind=d[v];//找出与pos相连的点的最小标号

        }

    }

    if(lv==flow)//没有找到增广路劲，进行标号更新

    {

        --gap[d[pos]];

        if(!gap[d[pos]])

            d[source]=n;

        d[pos]=mind+;

        ++gap[d[pos]];

    }

    return flow-lv;

}

int sap(int st,int de)

{

    source=st;

    des=de;

    memset(d,,sizeof(d));

    memset(gap,,sizeof(gap));

    gap[]=n;//初始标号为0的有n个.

    int ans=;

    while(d[st]<n)

    {

        ans+=dfs(st,inf);

        //cout<<d[st]<<endl;

    }

    return ans;

}

void init()

{

    e=;

    memset(index,-,sizeof(index));

}

int pos(int a,int b)

{

    return (a-)*m+b;

}

int main()

{

    int t,i,j;

    while(scanf("%d",&m)!=EOF)

    {

        init();

        int w;

        int sum=;

        for(i=;i<=m;i++)

            for(j=;j<=m;j++)

            {

                scanf("%d",&w);

                sum+=w;

                if((i+j)%==)

                {

                    addedge(,pos(i,j),w);

                    if(i<m)

                        addedge(pos(i,j),pos(i+,j),inf);

                    if(j<m)

                        addedge(pos(i,j),pos(i,j+),inf);

                    if(i>)

                        addedge(pos(i,j),pos(i-,j),inf);

                    if(j>)

                        addedge(pos(i,j),pos(i,j-),inf);

                }

                else

                    addedge(pos(i,j),m*m+,w);

            }

            n=m*m+;

        printf("%d\n",sum-sap(,n-));

    }

    return ;

}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

int s[<<];

int map[][];

int dp[][<<];

int main()

{

    int n,i,j,t,k,num=;;

    n=<<;

    for(i=;i<=n;i++)//记录可行状态

        if((i&(i<<))==)

            s[num++]=i;

    while(scanf("%d",&n)!=EOF)

    {

        for(i=;i<n;i++)

            for(j=;j<n;j++)

                scanf("%d",&map[i][j]);

        int p=;

        memset(dp,,sizeof(dp));

        for(i=;i<n;i++)//枚举每一行

        {

            p^=;//进行滚动数组

            for(j=;j<num;j++)//枚举每行的所有状态

            {

                if(s[j]>(<<n))

                    break;

                int sum=;

                for(k=;k<n;k++) if(s[j]&(<<k)) sum+=map[i][k];//记录该状态值

                for(k=;k<num;k++)//枚举已经得到的状态转移到该状态能到的最大值

                {

                    if(s[k]>(<<n))

                        break;

                    if(!(s[k]&s[j]))

                        dp[p][s[j]]=max(dp[p][s[j]],dp[-p][s[k]]+sum);

                }

            }

        }

        int ans=;

        for(i=;i<num&&s[i]<=(<<n);i++)//寻找答案

            ans=max(ans,dp[p][s[i]]);

        printf("%d\n",ans);

    }

    return ;

}