#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[weight[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[sz[mid]]<src)
l=mid+1;
else
r=mid-1;
}
return l-1;
}
bool check(int curr,int & A,int & B,int & T)
{
//cout<<"curr "<<curr<<endl;
for(int i=0;i<T;i++)
used[i]=false;
int cnt;
int idx=bin_search_w(x[A-1],T);
for(int i=A-1;i>=0;i--)
{
cnt=0;
while(idx>=0 && cnt<curr)
{
if(w[weight[idx]]<x[i] && !used[weight[idx]])
{
used[weight[idx]]=true;
cnt++;
}
idx--;
//cout<<"x "<<x[i]<<' '<<weight[idx]<<endl;
}
}
idx=bin_search_s(y[B-1],T);
for(int i=B-1;i>=0;i--)
{
cnt=0;
while(idx>=0 && cnt<curr)
{
if(s[sz[idx]]<y[i] && !used[sz[idx]])
{
used[sz[idx]]=true;
cnt++;
}
idx--;
//cout<<"y "<<y[i]<<' '<<sz[idx]<<endl;
}
}
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);
sort(x,x+A);
sort(y,y+B);
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;
}
