## 【COGS 396】[网络流24题] 魔术球问题（简化版

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100000;
const int INF = 10000000;

int n,m,S,T; queue<int> que;

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

#define id(x,ty) ((x)*2+ty)
inline int Add_Edge(int u, int v, int f) {
static int TT = 1;
to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = 1;
to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0;
return TT - 1;
}

inline bool BFS(){
memset(dis,-1,sizeof(dis));
que.push(S); dis[S] = 0;
while (!que.empty()) {
int w = que.front(); que.pop();
for (int i=head[w];i;i=nxt[i]) if (flow[i] && !~dis[to[i]])
dis[to[i]]  = dis[w] + 1, que.push(to[i]);
} return ~dis[T];
}

inline int DFS(int w, int f) {
if (w == T) return f;
else {
int ret = 0;
for (int &i=head[w];i;i=nxt[i]) if (flow[i] && dis[to[i]] == dis[w] + 1) {
int tmp = DFS(to[i], min(f, flow[i]));
flow[i] -= tmp; flow[i^1] += tmp; ret += tmp; f -= tmp;
if (!f) break;
} return ret;
}
}

inline int Dinic(){
int ret = 0;
while (BFS()) {
ret += DFS(S,INF);
} return ret;
}

int main(){
freopen("balla.in","r",stdin);
freopen("balla.out","w",stdout);
n = read(); S = 0; T = 1;
for (int i=1,w=0;i<=1600;i++) {