#include "robots.h"
#include <bits/stdc++.h>
#include <vector>
const int N = 1e6 + 6 ;
int AA , BB , TT ;
int XX[N] , YY[N] , WW[N] , SS[N] ;
using namespace std ;
bool check(int x){
set< pair<int, int > > fr , se;
for(int i = 0 ; i < TT ; i++){
fr.insert({WW[i] , i }) ;
}
for(int i = 0 ; i < AA && fr.size(); i++){
set<pair<int , int > > ::iterator j = fr.lower_bound({XX[i] , -1e7} ) ;
if(j==fr.begin())continue ;
j = prev(j) ;
vector<int> aux ;
int k = x ;
while(k--){
aux.push_back((*j).second) ;
if(j==fr.begin())
break;
j = prev(j) ;
}
for(auto u : aux)
fr.erase({WW[u] , u}) ;
}
for(auto u : fr){
se.insert({SS[u.second] , u.second}) ;
}
for(int i = 0 ; i < BB && se.size(); i++){
set<pair<int, int > > ::iterator j = se.lower_bound({YY[i] , -1e7});
if(j==se.begin())continue ;
j = prev(j) ;
vector<int> aux ;
int k = x ;
while(k--){
aux.push_back((*j).second) ;
if(j==se.begin())
break;
j = prev(j) ;
}
for(auto u : aux)
se.erase({SS[u] , u}) ;
}
return !se.size() ;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
AA = A ; BB= B ; TT = T ;
for(int i = 0 ; i < A ; i++)
XX[i] = X[i] ;
for(int i = 0 ; i < B ; i++)
YY[i] = Y[i] ;
for(int i = 0 ; i < T ; i++){
WW[i] = W[i] ;
SS[i] = S[i] ;
}
int l = 1 , r = T ;
int ans = -1;
while(l<=r){
int mid = l + (r-l) /2;
if(check(mid)){
ans = mid ;
r = mid - 1 ;
}
else{
l = mid + 1 ;
}
}
return ans ;
}
/*
int main()
{
freopen("robots.in" , "r" , stdin);
cin>>AA>>BB>>TT;
for(int i = 0 ; i < AA ; i++)
cin>>XX[i] ;
for(int i = 0 ; i < BB ; i++)
cin>>YY[i] ;
for(int i = 0 ; i < TT ; i++)
{
cin>>WW[i]>>SS[i];
}
cout<<putaway(AA ,BB , TT , XX , YY , WW , SS) ;
}*/
