#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
const int maxn=1e6+5;
const int maxa=5e4+5;
int w[maxn],s[maxn];
int x[maxa],y[maxa];
int sz[maxn],weight[maxn];
bool used[maxn];
bool cmpsz(int a,int b)
{
if(s[a]!=s[b])
return s[a]<s[b];
return w[a]<w[b];
}
bool cmpw(int a,int b)
{
if(w[a]!=w[b])
return w[a]<w[b];
return s[a]<s[b];
}
int bin_search_w(int src,int & T)
{
int l=0,r=T-1,mid;
while(l<=r)
{
mid=(l+r)/2;
if(w[mid]<src)
l=mid+1;
else
r=mid-1;
}
return l-1;
}
int bin_search_s(int src,int & T)
{
int l=0,r=T-1,mid;
while(l<=r)
{
mid=(l+r)/2;
if(s[mid]<src)
l=mid+1;
else
r=mid-1;
}
return l-1;
}
bool check(int curr,int & A,int & B,int & T)
{
for(int i=0;i<T;i++)
used[i]=false;
int cnt;
for(int i=0;i<A;i++)
{
int idx=bin_search_w(x[i],T);
cnt=0;
while(idx>=0 && cnt<curr)
{
if(!used[idx])
{
used[idx]=true;
cnt++;
}
idx--;
}
}
for(int i=0;i<B;i++)
{
int idx=bin_search_s(y[i],T);
cnt=0;
while(idx>=0 && cnt<curr)
{
if(!used[idx])
{
used[idx]=true;
cnt++;
}
idx--;
}
}
for(int i=0;i<T;i++)
{
if(!used[i])
return false;
}
return true;
}
int putaway(int A, int B, int T,int X[], int Y[], int W[], int S[])
{
for(int i=0;i<A;i++)
x[i]=X[i];
for(int i=0;i<B;i++)
y[i]=Y[i];
for(int i=0;i<T;i++)
{
sz[i]=i;
weight[i]=i;
w[i]=W[i]; s[i]=S[i];
}
sort(sz,sz+T,cmpsz);
sort(weight,weight+T,cmpw);
int l=1,r=T,mid;
while(l<=r)
{
mid=(l+r)/2;
if(check(mid,A,B,T))
r=mid-1;
else
l=mid+1;
}
if(l>T)
return -1;
return l;
}
