#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;
if(idx<=0)return;
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));
set<int>sr;
int op=(int)small.size();
int cnt[MAXN];
memset(cnt,0,sizeof(cnt));
for(int i=0;i<small.size();++i)sr.insert(-i);
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(query(j)<=0)
{
continue;
}
else
{
if(moves==1)cout<<query(MAXN-1)<<endl;
used[i]=1;
update(j,-1);
}*/
auto it=sr.lower_bound(s);
if(it==sr.end())continue;
used[i]=1;
int val=(*it);
--cnt[-val];
if(cnt[-val]==0)sr.erase(val);
--op;
//if(moves==1)cout<<op<<endl;
}
int j=0;
int cnt1=moves;
vector<int>small_taken,weak_taken;
for(int i=0;i<toys.size();++i)
{
/*if(moves==1)
{
if(used[i])
{
cout<<toys[i].w<<" "<<toys[i].s<<" S\n";
small_taken.push_back(toys[i].s);
}
else
{
cout<<toys[i].w<<" "<<toys[i].s<<" W\n";
weak_taken.push_back(toys[i].w);
}
}*/
if(used[i])continue;
if(j>=weak.size())return 0;
if(cnt1==0&&j==weak.size()-1)return 0;
if(cnt1==0)
{
cnt1=moves;
++j;
}
if(toys[i].w>weak[j])return 0;
--cnt1;
}
/*if(moves==1)
{
sort(weak_taken.rbegin(),weak_taken.rend());
sort(small_taken.rbegin(),small_taken.rend());
if(weak_taken.size()>weak.size())cout<<"wtf1\n";
if(small_taken.size()>small.size())cout<<"wtf2\n";
}*/
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());
for(int i=0;i<toys.size();++i)
{
int low=0,high=weak.size()-1,mid,best=-1;
while(low<=high)
{
mid=(low+high)/2;
if(weak[mid]>=toys[i].w)
{
best=mid;
low=mid+1;
}
else high=mid-1;
}
if(best!=-1)toys[i].w=weak[best];
else toys[i].w=2000000001;
}
sort(small.rbegin(),small.rend());
for(int i=0;i<toys.size();++i)
{
int low=0,high=small.size()-1,mid,best=-1;
while(low<=high)
{
mid=(low+high)/2;
if(small[mid]>=toys[i].s)
{
best=mid;
low=mid+1;
}
else high=mid-1;
}
toys[i].s=-best;
}
sort(toys.rbegin(),toys.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;
}
