#include "robots.h"
#include<bits/stdc++.h>
using namespace std;
struct edge{
int u,v,f;
};
vector<edge> edg;
vector<int> G[11115];
void ae(int u,int v,int f){
// cout<<"addedge: "<<u<<" "<<v<<" "<<f<<endl;
G[u].push_back(edg.size());
edg.push_back({u,v,f});
G[v].push_back(edg.size());
edg.push_back({v,u,0});
}
int idx[11115],vis[11115],dep[11115];
bool bfs(int s,int t,int z){
vis[s]=z; dep[s]=1;
queue<int> q; q.push(s);
while(q.size()){
int now=q.front(); q.pop();
for(int eid:G[now]){
edge &e=edg[eid];
if(vis[e.v]!=z && e.f>0){
q.push(e.v);
vis[e.v]=z;
dep[e.v]=dep[now]+1;
}
}
}
// cout<<"finish bfs"<<endl;
return (vis[t]==z);
}
int dfs(int now,int fl,int dis){
if(now==dis)return fl;
if(!fl)return 0;
int rt=0;
for(int &i=idx[now];i<G[now].size();++i){
int eid=G[now][i];
edge &e=edg[eid];
if(dep[e.v]==dep[now]+1 && e.f>0){
int f=dfs(e.v,min(fl,e.f),dis);
rt+=f; fl-=f;
e.f-=f;
edg[eid^1].f+=f;
if(!fl)return rt;
}
}
return rt;
}
int flow(int s,int t){
int vis_ptr=0,ans=0;
while(bfs(s,t,++vis_ptr)){
memset(idx,0,sizeof(idx));
ans+=dfs(s,1e9,t);
}
return ans;
}
int putaway(int a, int b, int t, int x[], int y[], int w[], int s[]) {
// cout<<"in: putaway"<<endl;
for(int i=0;i<a;++i){
for(int j=0;j<t;++j){
if(w[j]<x[i])ae(t+i,j,1);
}
}
for(int i=0;i<b;++i){
for(int j=0;j<t;++j){
if(s[j]<y[i])ae(t+a+i,j,1);
}
}
for(int i=0;i<t;++i)if(G[i].empty())return -1;
for(int i=0;i<t;++i)ae(i,11114,1);
for(int i=0;i<a;++i)ae(11113,t+i,0);
for(int i=0;i<b;++i)ae(11113,t+a+i,0);
int f=0;
for(int T=1;;++T){
for(int eid:G[11113])++edg[eid].f;
f+=flow(11113,11114);
if(f==t)return T;
}
}
