#include "robots.h"
#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
const int N=(1<<16);
int M[2*N], lazy[2*N];
void init(){
for(int i=0; i<2*N; i++){
M[i]=0;
lazy[i]=0;
}
}
void prop(int v){
if(v>=N)return;
int l=2*v, r=2*v+1;
lazy[l]+=lazy[v];
lazy[r]+=lazy[v];
M[l]+=lazy[v];
M[r]+=lazy[v];
lazy[v]=0;
}
void add(int v, int L, int R, int l, int r, int c){
if(l==L && r==R){
lazy[v]+=c;
M[v]+=c;
return;
}
int m=(L+R)>>1;
prop(v);
if(l<=m)add(2*v, L, m, l, min(r, m), c);
if(r>m)add(2*v+1, m+1, R, max(m+1, l), r, c);
M[v]=min(M[2*v], M[2*v+1]);
return;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
sort(X, X+A);
sort(Y, Y+B);
pair<int, int> tab[T];
for(int i=0; i<T; i++){
tab[i]={upper_bound(X, X+A, W[i])-X, upper_bound(Y, Y+B, S[i])-Y};
if(tab[i].st==A&&tab[i].nd==B)return -1;
//cout<<tab[i].st<<" "<<tab[i].nd<<"\n";
}
sort(tab, tab+T);
int l=1, r=A+B;
while(l<r){
int m=(l+r)/2;
init();
bool b=1;
int j=A-1;
for(int i=0; i<B; i++){
add(1, 0, N-1, 0, i, m);
}
//cout<<m<<"\n";
for(int i=T-1; i>=0; i--){
while(j>=0 && j>=tab[i].st)add(1, 0, N-1, 0, B, m), j--;
add(1, 0, N-1, 0, tab[i].nd, -1);
/*for(int i=0; i<2*N; i++)cout<<M[i]<<" ";
cout<<"\n";
for(int i=0; i<2*N; i++)cout<<lazy[i]<<" ";
cout<<"\n";*/
if(M[1]<0){
b=0;
//cout<<i<<"\n";
break;
}
}
//cout<<m<<" "<<b<<"\n";
if(b)r=m;
else l=m+1;
}
return l;
}
