#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
#include "robots.h"
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=1e6+50;
const int mmax=5e4+50;
const int mod=1e9+7;
using namespace std;
int n,m,i,j,na,nb,we[mmax],sm[mmax],s[nmax],w[nmax],nr[mmax],l,r,mid,b[nmax],rs,st[4*mmax];
pair<int,int>a[nmax],aa[nmax];
pair<pair<int,int>,int>v[nmax];
bitset<nmax>vz;
void upd(int nod,int l,int r,int p,int v)
{
if(l==r)
{
st[nod]=v;
return;
}
int mid=(l+r)/2;
if(p<=mid)upd(2*nod,l,mid,p,v);
else upd(2*nod+1,mid+1,r,p,v);
st[nod]=st[2*nod]+st[2*nod+1];
}
int qry(int nod,int l,int r,int tl,int tr)
{
if(tr<l || tl>r)return 0;
if(tl<=l && r<=tr)return st[nod];
int mid=(l+r)/2;
return qry(2*nod,l,mid,tl,tr)+qry(2*nod+1,mid+1,r,tl,tr);
}
int kth(int x,int l,int r,int k)
{
if(st[x]<k)return -1;
if(l==r)return l;
int mid=(l+r)/2;
if(st[2*x]>=k)return kth(2*x,l,mid,k);
else return kth(2*x+1,mid+1,r,k-st[2*x]);
}
int ok(int x)
{
int i,y,z,j,tot=0,u;
for(i=1;i<=na;i++)
{
upd(1,1,na,i,1);
nr[i]=0;
}
vz.reset();
for(i=1;i<=m;i++)
{
if(v[i].sc>1)z=qry(1,1,na,1,v[i].sc-1)+1;
else z=1;
y=kth(1,1,na,z);
if(y==-1)continue;
nr[y]++;
if(nr[y]==x)upd(1,1,na,y,0);
vz[v[i].fr.sc]=1;
tot++;
}
u=0;
for(i=1;i<=n;i++)
{
if(vz[aa[i].sc])continue;
b[++u]=aa[i].fr;
}
if(u)
{
j=1;
for(i=1;i<=nb;i++)
{
z=0;
for(;j<=u;j++)
{
if(b[j]>=sm[i])break;
if(z==x)break;
z++;
tot++;
}
}
}
return (tot==n);
}
int putaway(int Na,int Nb,int N,int We[],int Sm[],int W[],int S[])
{
na=Na,nb=Nb,n=N;
if(na>nb)
{
swap(na,nb);
swap(We,Sm);
swap(W,S);
}
for(i=1;i<=na;i++)we[i]=We[i-1];
for(i=1;i<=nb;i++)sm[i]=Sm[i-1];
for(i=1;i<=n;i++)
{
w[i]=W[i-1],s[i]=S[i-1];
a[i]=mkp(w[i],i);
aa[i]=mkp(s[i],i);
}
sort(a+1,a+n+1);
sort(we+1,we+na+1);
sort(sm+1,sm+nb+1);
sort(aa+1,aa+n+1);
m=1;
for(i=1;i<=na;i++)
{
for(;m<=n;m++)
{
if(we[i]<=a[m].fr)break;
v[m]=mkp(mkp(s[a[m].sc],a[m].sc),i);
}
}
m--;
sort(v+1,v+m+1);
reverse(v+1,v+m+1);
if(!ok(n))return -1;
l=1,r=n;
while(l<=r)
{
mid=(l+r)/2;
if(ok(mid))r=mid-1;
else l=mid+1;
}
return r+1;
}
