#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
#define fi first
#define se second
#define sz(x) (int)x.size()
using ii = pair<int,int>;
const int mxn = 1e6+5;
int n;
ii val[mxn];
struct node{
int x,y;
node(int x_, int y_):x(x_),y(y_){
}
bool operator < (const node &rhs)const{
return y<rhs.y;
}
};
bool works(int tar, int x[], int a, int y[], int b){
priority_queue<node>pq;
//cerr<<tar<<": \n";
int ptr = 0;
for(int i=0; i<a; i++){
while(ptr<n&&val[ptr].fi<x[i])pq.emplace(node(val[ptr].fi,val[ptr].se)),ptr++;
int cnt = 0;
while(cnt<tar){
if(!pq.empty())pq.pop(),cnt++;
else break;
}
}
while(ptr<n)pq.emplace(node(val[ptr].fi,val[ptr].se)),ptr++;
for(int i=0; i<b; i++){
int cnt = 0;
while(cnt<tar){
if(!pq.empty()&&pq.top().y<y[i])pq.pop(),cnt++;
else break;
}
}
//cerr<<sz(pq)<<"\n";
return sz(pq)==0;
}
int putaway(int A,int B,int T, int X[],int Y[],int W[],int S[]){
sort(X,X+A);
sort(Y,Y+B,greater<int>());
n=T;
for(int i=0; i<T; i++){
val[i]={W[i],S[i]};
}
sort(val,val+n,[&](const ii x, const ii y){
return x.fi<y.fi;
});
int lo = 1, hi = T+5, ans = T;
if(!works(T,X,A,Y,B))return -1;
while(lo<=hi){
int mid=(lo+hi)/2;
if(works(mid,X,A,Y,B)){
hi=mid-1;
ans = mid;
}else{
lo=mid+1;
}
}
return ans;
}
/*
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n2,m2,t2; cin>>n2>>m2>>t2;
int x2[n2],y2[m2],w2[t2],s2[t2];
for(int i=0; i<n2; i++)cin>>x2[i];
for(int i=0; i<m2; i++)cin>>y2[i];
for(int i=0; i<t2; i++)
cin>>w2[i]>>s2[i];
cout<<putaway(n2,m2,t2,x2,y2,w2,s2)<<endl;
return 0;
}
// */
//check for -1 both w[i]&s[i] exceed largest x[i]&y[i]
