#include<bits/stdc++.h>
#include "robots.h"
#define MAXN 1000007
using namespace std;
struct edge{
int to;
bool cap;
int rev;
};
struct toy{
int x,y,id;
inline friend bool operator < (toy fr,toy sc){
return fr.y<sc.y;
}
};
int n,m,k,maxb;
int x[MAXN],y[MAXN];
toy s[MAXN],t[MAXN];
bool is[MAXN];
priority_queue<toy> q;
bool cmp(toy fr,toy sc){
return fr.x<sc.x;
}
bool cmp2(toy fr,toy sc){
return fr.y<sc.y;
}
bool check(int days){
while(!q.empty())q.pop();
for(int i=1;i<=k;i++)is[i]=false;
int pt=1;
for(int i=1;i<=n;i++){
while(pt<=k and x[i]>s[pt].x){
q.push(s[pt]); pt++;
}
for(int f=1;f<=days and !q.empty();f++)q.pop();
}
while(pt<=k){
q.push(s[pt]); pt++;
}
while(!q.empty()){
is[q.top().id]=true;
q.pop();
}
pt=m;
int br=days;
for(int i=k;i>=1;i--){
if(!is[t[i].id])continue;
if(br==0){
br=days; pt--;
}
if(y[pt]<=t[i].y)return false;
br--;
}
return true;
}
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];
maxb=max(maxb,y[i]);
}
for(int i=1;i<=k;i++)s[i]=t[i]={W[i-1],S[i-1],i};
sort(x+1,x+n+1);
sort(y+1,y+m+1);
sort(s+1,s+k+1,cmp);
sort(t+1,t+k+1,cmp2);
if(x[n]<=s[k].x and y[m]<=s[k].y)return -1;
if(x[n]<=t[k].x and y[m]<=t[k].y)return -1;
int l=0,r=k+1,tt;
while(l+1<r){
tt=(l+r)/2;
if(check(tt))r=tt;
else l=tt;
}
return r;
}
/*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;
}*/
