#include "soccer.h"
#include <bits/stdc++.h>
int dp[32][32][32][32];
int biggest_stadium(int N, std::vector<std::vector<int>> F) {
	memset(dp,-0x3f,sizeof(dp));
	for(int i=1;i<=N;i++) {
		for(int j=1;j<=N;j++) {
			for(int k=j;k<=N;k++) {
				if(F[i-1][k-1]) break;
				dp[i][i][j][k]=k-j+1;
			}
		}
	}
	int as=0;
	for(int l=1;l<=N;l++) {
		for(int i=1;i+l-1<=N;i++) {
			int j=i+l-1;
			for(int k=1;k<=N;k++) {
				for(int x=k;x<=N;x++) {
					as=std::max(as,dp[i][j][k][x]);
					if(dp[i][j][k][x]<0) continue;
					for(int l=k;l<=x;l++) {
						int z1=0,z2=0;
						for(int r=l;r<=x;r++) {
							if((i==1)||F[i-2][r-1]) z1=1;
							if((j==N)||F[j][r-1]) z2=1;
							if(!z1) {
								dp[i-1][j][l][r]=std::max(dp[i-1][j][l][r],
									dp[i][j][k][x]+r-l+1);
							}
							if(!z2) {
								dp[i][j+1][l][r]=std::max(dp[i][j+1][l][r],
									dp[i][j][k][x]+r-l+1);
							}
						}
					}
				}
			}
		}
	}
    return as;
}