#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long int ll;
int a,b,t;
int x[50010],y[50010];
pii ty[1000010];
int bs_x(int val)
{
if(x[a]<=val) return a+1;
int hi=a,low=1,av;
while(hi>low)
{
av=(hi+low)>>1;
if(x[av]>val) hi=av;
else low=av+1;
}
return hi;
}
int bs_y(int val)
{
if(y[b]<=val) return b+1;
int hi=b,low=1,av;
while(hi>low)
{
av=(hi+low)>>1;
if(y[av]>val) hi=av;
else low=av+1;
}
return hi;
}
priority_queue<int> pq;
bool test_min(int k)
{
int id=1,cou,to;
for(int i=1;i<=a;i++)
{
while(ty[id].first==i)
{
pq.push(ty[id].second);
id++;
}
cou=k;
while(cou && !pq.empty())
{
pq.pop();
cou--;
}
}
while(id<=t)
{
pq.push(ty[id].second);
id++;
}
int co=0;
while(!pq.empty())
{
to=pq.top();
pq.pop();
co++;
if((ll)co>(ll)k*(ll)(b+1-to)) return false;
}
return true;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
a=A;
b=B;
t=T;
for(int i=0;i<a;i++) x[i+1]=X[i];
for(int i=0;i<b;i++) y[i+1]=Y[i];
sort(x+1,x+a+1);
sort(y+1,y+b+1);
for(int i=0;i<t;i++)
{
ty[i+1]={bs_x(W[i]),bs_y(S[i])};
if(ty[i+1].first==a+1 && ty[i+1].second==b+1) return -1;
}
sort(ty+1,ty+t+1);
int hi=t,low=1,av;
while(hi>low)
{
av=(hi+low)>>1;
if(test_min(av)) hi=av;
else low=av+1;
}
return hi;
}
