#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10 , M = 5e4 + 10;
int a , b , t , x[M] , y[M] , cx[M] , cy[M];
struct item{
int w , s;
} ar[N];
bool cmp(item aa , item bb)
{
return aa.s > bb.s;
}
bool Check(int mid)
{
set <int> X , Y;
//cout << mid << " : " << endl;
for(int i = 0 ; i < a ; i++)
{
cx[i] = mid;
X.insert(i);
}
for(int i = 0 ; i < b ; i++)
{
cy[i] = mid;
Y.insert(i);
}
bool flg = true;
for(int i = 0 ; i < t ; i++)
{
int A = upper_bound(x , x + a , ar[i].w) - x;
int B = upper_bound(y , y + b , ar[i].s) - y;
//cout << i << " " << A << " " << B << endl;
auto ita = X.lower_bound(A);
auto itb = Y.lower_bound(B);
if(ita != X.end())
{
auto now = *ita;
cx[now]--;
if(cx[now] == 0)
X.erase(ita);
}
else if(itb != Y.end())
{
auto now = *itb;
cy[now]--;
if(cy[now] == 0)
Y.erase(itb);
}
else
{
flg = false;
break;
}
}
return flg;
}
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] = X[i];
for(int i = 0 ; i < b ; i++)
y[i] = Y[i];
sort(x , x + a);
sort(y , y + b);
for(int i = 0 ; i < T ; i++)
{
ar[i] = {W[i] , S[i]};
}
sort(ar , ar + T , cmp);
int low = 0 , high = T + 1;
while(high - low > 1)
{
int mid = (low + high) >> 1;
if(Check(mid))
high = mid;
else
low = mid;
}
if(high == T + 1)
return -1;
return high;
}
