#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 idx=0,cnt;
set<pair<int,int>,greater<pair<int,int>>>st;
for(int i=0;i<A;i++)
{
while(idx<T && w[weight[idx]]<x[i])
{
if(!used[weight[idx]])
{
st.insert({s[weight[idx]],weight[idx]});
}
idx++;
}
cnt=0;
while(!st.empty() && cnt<curr)
{
pair<int,int> ch=*(st.begin());
used[ch.second]=true;
st.erase(st.begin());
cnt++;
}
}
idx=0;
st.clear();
for(int i=0;i<B;i++)
{
while(idx<T && s[sz[idx]]<y[i])
{
if(!used[sz[idx]])
{
st.insert({w[sz[idx]],sz[idx]});
}
idx++;
}
cnt=0;
while(!st.empty() && cnt<curr)
{
pair<int,int> ch=*(st.begin());
used[ch.second]=true;
st.erase(st.begin());
cnt++;
}
}
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;
}
