#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
int n,a,b;
pair<int, int> val[1000005];
int weak[50005];
int small[50005];
bool comp(int x, int y)
{
return val[x].first < val[y].first;
}
bool ok(int nr)
{
/*
cout<<"debug\n";
for(int i=1;i<=a;i++)
cout<<weak[i]<<' ';
cout<<"\n\n";
for(int i=1;i<=b;i++)
cout<<small[i]<<' ';
cout<<"\n\n";
for(int i=1;i<=n;i++)
cout<<val[i].first<<' '<<val[i].second<<'\n';
cout<<'\n';
*/
int j=1;
multiset<int> s;
for(int i=1; i<=a; i++)
{
while(j<=n && val[j].first < weak[i])
{
s.insert(val[j].second);
j++;
}
int cnt = nr;
while(!s.empty() && cnt)
{
cnt--;
auto it = s.end();
it--;
s.erase(it);
}
}
while(j <= n)
{
s.insert(val[j].second);
j++;
}
/*
cout<<"s ramas\n";
for(int it : s)
cout<<it<<' ';
cout<<'\n';
*/
for(int i=1; i<=b; i++)
{
int cnt = nr;
while(!s.empty() && cnt)
{
cnt--;
auto it = s.lower_bound(small[i]);
if(it == s.begin())
break;
it--;
s.erase(it);
}
}
if(s.empty())
return true;
else
return false;
}
int putaway(int A, int B, int N, int X[], int Y[], int W[], int S[])
{
a = A;
b = B;
n = N;
for(int i=1;i<=n;i++)
val[i] = {W[i-1], S[i-1]};
sort(val+1, val+n+1);
for(int i=1;i<=a;i++)
weak[i] = X[i-1];
sort(weak+1, weak+a+1);
for(int i=1;i<=b;i++)
small[i] = Y[i-1];
sort(small+1, small+b+1);
for(int i=1;i<=n;i++)
if(val[i].first >= weak[a] && val[i].second >= small[b])
return -1;
//cout<<ok(2)<<'\n';
//return 0;
int st=1, dr=n, mij, last=1;
while(st <= dr)
{
mij = (st+dr)/2;
if(ok(mij))
{
last = mij;
dr = mij-1;
}
else
st = mij+1;
}
return last;
}
