未过样例。。。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[10][10],n,dp[10][10][10][10][20],book[10][10][10][10][20];
ll dfs(ll s1,ll s2,ll e1,ll e2,ll cs){
	if(abs(s2-s1)==0 && abs(e2-e1)==0 && cs>=1)  return -1;
	if(book[s1][s2][e1][e2][cs]==1)  return  dp[s1][s2][e1][e2][cs];
	if(cs==0){
		ll pos=0;
		for(int i=s1;i<=s2;i++){
			for(int j=e1;j<=e2;j++){
				pos+=a[i][j];
			}
		}
		book[s1][s2][e1][e2][cs]=1;
		dp[s1][s2][e1][e2][cs]=pos*pos;
		cout<<s1<<" "<<s2<<" "<<e1<<" "<<e2<<endl;
		cout<<pos*pos<<endl;
		return pos*pos;
	}
	ll minn=10000000000000;
	for(int i=s1+1;i<=s2;i++){
		if(dfs(s1,i-1,e1,e2,cs-1)!=-1 && dfs(i,s2,e1,e2,0)!=-1)minn=min(minn,dfs(s1,i-1,e1,e2,cs-1)+dfs(i,s2,e1,e2,0));
		if(dfs(s1,i-1,e1,e2,0)!=-1 && dfs(i,s2,e1,e2,cs-1)!=-1)minn=min(minn,dfs(s1,i-1,e1,e2,0)+dfs(i,s2,e1,e2,cs-1));
	}
	for(int i=e1+1;i<=e2;i++){
		if(dfs(s1,s2,e1,i-1,cs-1)!=-1 && dfs(s1,s2,i,e2,0)!=-1)minn=min(minn,dfs(s1,s2,e1,i-1,cs-1)+dfs(s1,s2,i,e2,0));
		if(dfs(s1,s2,e1,i-1,0)!=-1 && dfs(s1,s2,i,e2,cs-1)!=-1)minn=min(minn,dfs(s1,s2,e1,i-1,0)+dfs(s1,s2,i,e2,cs-1));
	}
	if(minn!=10000000000000){
		book[s1][s2][e1][e2][cs]=1;
		dp[s1][s2][e1][e2][cs]=minn;
		cout<<s1<<" "<<s2<<" "<<e1<<" "<<e2<<endl;
		cout<<minn<<endl<<1<<endl;
		return minn;
	}
	else{
		book[s1][s2][e1][e2][cs]=1;
		dp[s1][s2][e1][e2][cs]=-1;
		return -1;
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=8;i++){
		for(int j=1;j<=8;j++){
			cin>>a[i][j];
		}
	}
	cout<<dfs(1,8,1,8,n);
	return 0;
}