#include<bits/stdc++.h>
#include "robots.h"
#define MAXN 30007
using namespace std;
struct edge{
int to;
bool cap;
int rev;
};
int n,m,k;
int x[MAXN],y[MAXN];
pair<int,int> s[MAXN],t[MAXN];
bool cmp(pair<int,int> fr,pair<int,int> sc){
return fr.second<sc.second;
}
vector<edge> g[MAXN];
void add_edge(int from,int to){
g[from].push_back({to,1,int(g[to].size())});
g[to].push_back({from,0,int(g[from].size())-1});
}
int source,sink,flow,maxflow;
int li[MAXN],tim;
int dfs(int x){
if(x==sink)return 1;
li[x]=tim;
for(int i=0;i<g[x].size();i++){
if(li[g[x][i].to]==tim or !g[x][i].cap)continue;
int curr=dfs(g[x][i].to);
if(curr>0){
g[x][i].cap=false;
g[g[x][i].to][g[x][i].rev].cap=true;
return 1;
}
}
return 0;
}
bool check(int days){
int A=min(n*days,k);
int B=min(m*days,k);
source=0; sink=A+B+k+1;
for(int i=0;i<=sink;i++)g[i].clear();
for(int i=1;i<=A+B;i++)add_edge(source,i);
for(int i=1;i<=k;i++)add_edge(A+B+i,sink);
int pt=0;
for(int i=n;i>=1;i--){
for(int t=1;t<=days;t++){
pt++;
if(pt>k)break;
for(int f=1;f<=k;f++){
if(x[i]<=s[f].first)continue;
add_edge(pt,A+B+f);
}
}
}
pt=0;
for(int i=m;i>=1;i--){
for(int t=1;t<=days;t++){
pt++;
if(pt>k)break;
for(int f=1;f<=k;f++){
if(y[i]<=s[f].second)continue;
add_edge(A+pt,A+B+f);
}
}
}
maxflow=0;
while(true){
tim++;
flow=dfs(source);
if(flow==0)break;
maxflow+=flow;
}
return maxflow==k;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
//int putaway(int A, int B, int T, vector<int> X, vector<int> Y, vector<int> W, vector<int> S) {
n=A; m=B; k=T;
for(int i=1;i<=n;i++)x[i]=X[i-1];
for(int i=1;i<=m;i++)y[i]=Y[i-1];
for(int i=1;i<=k;i++)s[i]=t[i]={W[i-1],S[i-1]};
sort(x+1,x+n+1);
sort(y+1,y+m+1);
sort(s+1,s+k+1);
sort(t+1,t+k+1,cmp);
if(x[n]<=s[k].first and y[m]<=s[k].second)return -1;
for(int i=1;i<=k;i++){
if(check(i))return i;
}
return 0;
}
/*int main(){
cout<<putaway(3,2,10,{6,2,9},{4,7},{4,8,2,7,1,5,3,8,7,10},{6,5,3,9,8,1,3,7,6,5})<<"\n";
return 0;
}*/
