> /*
> 1.等价剪枝：根据对称性剪枝
> 2.无法达最优：提前剪枝 
> 3.换个角度，更高效搜索算法 ：如本题逆向思维求最小内部代价 
> */
> 
> #include <cstdio>
> #include <cstring>
> 
> int M[20][20],n,ans,arr1[20],arr2[20];
> 
> void dfs(int Sum,int p1,int p2,int cur)
> {
> 	if(Sum>=ans) 
> 		return;
> 	else if(cur==20)
> 		ans=Sum;
> 	else
> 	{
> 	    int sum,temp,temp1,temp2;
> 		
> 	    sum=0;
> 	    for(int i=0;i<p1;i++)
> 	    sum+=M[arr1[i]][cur];
> 	    temp1=arr1[p1];
>             arr1[p1]=cur;
> 	    dfs(Sum+sum,p1+1,p2,cur+1);
> 	    arr1[p1]=temp1;
> 	    
> 	    sum=0;
> 	    for(int i=0;i<p2;i++)
> 	    sum+=M[arr2[i]][cur];
> 	    temp2=arr2[p2];
> 	    arr2[p2]=cur;
> 	    dfs(Sum+sum,p1,p2+1,cur+1);
> 	    arr2[p2]=temp2;
> 	}
> }
> 
> int main(){
> 	int i,j,ans1,ans2,total=0;
> 	while(~scanf("%d",&n))
> 	{
> 		for(i=0;i<n;i++)
> 		    for(j=0;j<n;j++){
> 		        scanf("%d",&M[i][j]);total+=M[i][j];
> 		    }
> 		    
> 		ans1=0;
> 		for(i=0;i<n/2;i++)
> 			for(j=0;j<n/2;j++)
> 				ans1+=M[i][j];
> 		ans1/=2;
> 		
> 		ans2=0;
> 		for(i=n/2;i<n;i++)
> 		    for(j=n/2;j<n;j++)
> 		        ans2+=M[i][j];
> 		ans2/=2;
> 		        
> 		memset(arr1,0,sizeof(arr1));
> 		memset(arr2,0,sizeof(arr2));
> 		arr1[0]=0;
> 		ans=ans1+ans2;
> 		dfs(0,1,0,1);
> 		printf("%d\n",total/2-ans);
> 	}
> 	return 0;
> }
>