#include "soccer.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PLL;
typedef vector <int> vi;
typedef vector <vi> vvi;
#define pb push_back
#define fi first
#define se second
#define rep(i,a,b) for(int i = a;i < b;i++)
#define trav(nx, v) for(auto &nx : v)
#define all(a) begin(a), end(a)
#define sz(v) (int) v.size()

int n;
int presum[1005][1005];
void init(const vvi &stadium){
	for(int i = 0;i < n;i++){
		for(int j = 0;j < n;j++){
			presum[i + 1][j + 1] = stadium[i][j];
		}
	}
	rep(i,1,n + 1){
		rep(j,1,n + 1){
			presum[i][j] += presum[i - 1][j] + presum[i][j - 1] - presum[i - 1][j - 1];
		}
	}
}

LL query(PLL st, PLL ed){
	st.fi++; st.se++;
	ed.fi++; ed.se++;
	if(st.fi > ed.fi) swap(st.fi, ed.fi);
	if(st.se > ed.se) swap(st.se, ed.se);
	return presum[ed.fi][ed.se] - presum[st.fi - 1][ed.se] - presum[ed.fi][st.se - 1] + presum[st.fi - 1][st.se - 1];
}

bool check(const vvi &stadium){
			//~ rep(i,0,n) {
				//~ rep(j,0,n) cout << stadium[i][j];
				//~ cout << endl;
			//~ }
	rep(i,0,n){
		rep(j,0,n) {
			if(stadium[i][j] != 2) continue;
			rep(x,i,n){
				rep(y,0,n){
					if(x == i && y == j) continue;
					if(stadium[x][y] != 2) continue;
					bool bawah = query({i, j}, {x, j}) + query({x, j}, {x, y}) == 0;
					bool atas = query({i, j}, {i, y}) + query({i, y}, {x, y}) == 0;
						//~ cout << i << " " << j << " " << x << " " << y << " " << bawah << " " << atas << endl;
					if(!bawah && !atas) {
						
						//~ cout << i << " " << j << " " << x << " " << y << endl;
						//~ exit(0);	
						return 0;
					}
				}
			}
		}
	}
	return 1;
}

int biggest_stadium(int N, std::vector<std::vector<int>> F){
	vvi tmp = F;
	n = N;
	init(tmp);
	int ans = 0;
	rep(mask,1,(1<<(N * N))){
		rep(i,0,N) rep(j,0,N) if(tmp[i][j] == 2) tmp[i][j] = 0;
		bool can = 1;
		rep(i,0,N * N) if((mask>>i)&1 && tmp[i/N][i%N] == 1) can = 0;
		if(!can) continue;
		rep(i,0,N * N) if((mask>>i)&1 && tmp[i/N][i%N] == 0){
			tmp[i/N][i%N] = 2;
		}
		can = check(tmp);
		if(!can) continue;
		auto curans = __builtin_popcount(mask);
		if(curans > ans){
			ans = curans;
			//~ cout << "WT" << endl;
			//~ rep(i,0,N) {
				//~ rep(j,0,N) cout << tmp[i][j];
				//~ cout << endl;
			//~ }
		
		}
	}
    return ans	;
}