#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXT=1e6+6;
const int MAXN=5e4+6;
struct toy
{
int w,s;
bool operator<(const toy &other)const
{
if(w!=other.w)return w<other.w;
return s<other.s;
}
};
vector<toy>toys;
vector<int>weak,small;
bool used[MAXT];
int fen[MAXT];
void update(int idx,int val)
{
idx++;
for(;idx<MAXN;idx+=idx&(-idx))
{
fen[idx]+=val;
}
}
int query(int idx)
{
if(idx<0)return 0;
idx++;
int ret=0;
for(;idx>0;idx-=idx&(-idx))
{
ret+=fen[idx];
}
return ret;
}
bool ok(int moves)
{
memset(used,0,sizeof(used));
memset(fen,0,sizeof(fen));
for(int i=0;i<small.size();i++)update(i,moves);
for(int i=0;i<toys.size();i++)
{
int s=toys[i].s;
int low1=0,high1=small.size()-1,mid1,best1=-1;
while(low1<=high1)
{
mid1=(low1+high1)/2;
if(small[mid1]>=s)
{
best1=mid1;
low1=mid1+1;
}
else high1=mid1-1;
}
int j=best1;
/*if(j>=0)cout<<s<<" "<<small[j]<<endl;
else cout<<s<<" no\n";*/
if(query(j)<=0)
{
continue;
}
else
{
used[i]=1;
update(j,-1);
}
}
/*cout<<"moves "<<moves<<":\n";
for(int i=0;i<toys.size();i++)
{
cout<<toys[i].w<<" "<<toys[i].s<<" "<<used[i]<<endl;
}*/
int cnt=moves,j=0;
for(int i=0;i<toys.size();i++)
{
if(used[i])continue;
if(cnt==0&&j==weak.size()-1)return 0;
if(cnt==0)
{
cnt=moves;
j++;
}
//cout<<"-- "<<toys[i].w<<" "<<weak[j]<<endl;
if(toys[i].w>weak[j])return 0;
cnt--;
}
return 1;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
for(int i=0;i<T;i++)
{
toys.push_back({W[i],S[i]});
}
sort(toys.rbegin(),toys.rend());
for(int i=0;i<A;i++)weak.push_back(X[i]-1);
for(int i=0;i<B;i++)small.push_back(Y[i]-1);
sort(weak.rbegin(),weak.rend());
sort(small.rbegin(),small.rend());
int low=1,high=T,mid,best=T+1;
while(low<=high)
{
mid=(low+high)/2;
if(ok(mid))
{
best=mid;
high=mid-1;
}
else low=mid+1;
}
if(best==T+1)
{
return -1;
}
return best;
}
