#include "robots.h"
#include <bits/stdc++.h>
const int N = 1e6 + 6 ;
int AA , BB , TT ;
int XX[N] , YY[N] , WW[N] , SS[N] ;
using namespace std ;
struct DSU{
vector<int> fat ;
void init(int n){
fat.resize(n) ;
for(int i = 0 ; i < n; i++){
fat[i] = i ;
}
}
int fin(int x){
return fat[x] = (fat[x]==x?x:fin(fat[x]));
}
void unio(int a , int b){
int aa = fin(a) ;
int bb = fin(b) ;
if(aa!=bb){
fat[aa] = bb ;
}
}
};
bool check(int x){
vector< pair<int, int > > fr , se;
for(int i = 0 ; i < TT ; i++){
fr.push_back({WW[i] , i }) ;
}
sort(fr.begin() , fr.end()) ;
vector<int> vis(N , 0 );
DSU d1;
d1.init(TT+1) ;
for(int i = 0 ; i < AA; i++){
int j = (int)(lower_bound(fr.begin() , fr.end() , make_pair(XX[i] , 0) ) - fr.begin()) ;
if(!j)continue; j--;
j = d1.fin(j);
vector<int> aux;
int k = x ;
while(k-- && j>=0){
int r = fr[j].second ;
vis[r] ++ ;
if(j){
d1.unio(j , j-1);
j = d1.fin(j) ;
}
else break;
}
}
for(auto u : fr){
if(!vis[u.second]){
se.push_back({SS[u.second] , u.second}) ;
}
}
d1.init(TT+1);
for(int i = 0 ; i < BB; i++){
int j = (int)(lower_bound(se.begin() , se.end() , make_pair(YY[i] , 0) ) - se.begin()) ;
if(!j)continue; j--;
j = d1.fin(j);
vector<int> aux;
int k = x ;
while(k-- && j>=0){
int r = se[j].second ;
vis[r] ++ ;
if(j){
d1.unio(j , j-1);
j = d1.fin(j) ;
}
else break;
}
}
for(auto u : se){
if(!vis[u.second]){
return 0 ;
}
}
return 1;
}
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] ;
}
sort(XX , XX + AA) ;
sort(YY , YY + BB) ;
int l = 1 , r = T ;
int ans = -1;
while(l<=r){
int mid = (l+r) /2;
if(check(mid)){
ans = mid ;
r = mid - 1 ;
}
else{
l = mid + 1 ;
}
}
return ans ;
}
