#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
const int M = 1e6, inf=2e9+1;
int seg[M*4];
void modify(int p,int x,int v=1,int s=0,int e=M)
{
if (s+1==e)
{
seg[v]=x;
return;
}
int mid=(s+e)/2,lc=v*2,rc=v*2+1;
if (p<mid)
modify(p,x,lc,s,mid);
else
modify(p,x,rc,mid,e);
seg[v]=min(seg[lc],seg[rc]);
}
int get(int l,int r,int v=1,int s=0,int e=M)
{
if (e<=l or r<=s)
return inf;
if (l<=s and e<=r)
return seg[v];
int mid=(s+e)/2,lc=v*2,rc=v*2+1;
return min(get(l,r,lc,s,mid),get(l,r,rc,mid,e));
}
int putaway(int a, int b, int t, int x[], int y[], int w[], int s[])
{
int mx=0,mx1=0;
for (int i=0;i<a;i++)
mx=max(mx,x[i]);
for (int i=0;i<b;i++)
mx1=max(mx1,y[i]);
for (int i=0;i<t;i++)
if (w[i]>=mx and s[i]>=mx1)
return -1;
if (b==0)
{
int cnt[a]={};
sort(x,x+a);
for (int i=0;i<t;i++)
{
int it=upper_bound(x,x+a,w[i])-x;
cnt[it]++;
}
int ans=cnt[a-1],su=cnt[a-1];
for (int i=a-2;i>=0;i--)
{
int oops=min(cnt[i],ans*(a-i)-su);
cnt[i]-=oops;
su+=oops;
ans+=(cnt[i]+a-i-1)/(a-i);
su+=cnt[i];
}
return ans;
}
map<int,vector<int>> cnt;
vector<int> dsz;
for (int i=0;i<t;i++)
{
if (cnt.find(s[i])==cnt.end())
dsz.push_back(s[i]);
cnt[s[i]].push_back(w[i]);
}
int pre[1+(int)dsz.size()]={};
sort(dsz.begin(),dsz.end());
reverse(dsz.begin(),dsz.end());
int ind=0;
for (int i=0;i<dsz.size();i++)
{
for (int j:cnt[dsz[i]])
modify(ind++,j);
pre[i+1]=pre[i]+(int)cnt[dsz[i]].size();
}
sort(x,x+a);
sort(y,y+b);
int stt=0,e=t;
while (stt+1<e)
{
int mid=(stt+e)/2;
multiset<int> msz;
for (int i=0;i<t;i++)
msz.insert(s[i]);
ind=0;
for (int i=0;i<dsz.size();i++)
for (int j:cnt[dsz[i]])
modify(ind++,j);
for (int i=0;i<a;i++)
{
for (int j=0;j<mid;j++)
{
if (get(0,ind)>=x[i])
break;
int st=0,en=ind-1;
while (st+1<en)
{
int mid1=(st+en)/2;
if (get(0,mid1+1)<x[i])
en=mid1;
else
st=mid1;
}
modify(en,inf);
int it=upper_bound(pre,pre+1+(int)dsz.size(),en)-pre;
msz.erase(msz.find(dsz[it-1]));
}
}
for (int i=0;i<b;i++)
for (int j=0;j<mid;j++)
{
auto it=msz.lower_bound(y[i]);
if (it!=msz.begin())
{
it--;
msz.erase(it);
}
else
break;
}
if (msz.empty())
e=mid;
else
stt=mid;
}
return e;
}
