#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
#define MAX_T 1000006
#define MAX_A 50004
#define We first
#define Si second
int A ,B ,T;
int Weak[MAX_A];
int Small[MAX_A];
pair <int ,int> WeTs[MAX_T];
bool can(int X)
{
int Weak_ptr = 0;
priority_queue <int> pq;
for(int i=0; i<A; i++)
{
while(Weak_ptr < T && WeTs[Weak_ptr].We < Weak[i])
pq.push(WeTs[Weak_ptr++].Si);
int CanHave = X;
while(!pq.empty() && CanHave--)
pq.pop();
}
while(Weak_ptr < T)
pq.push(WeTs[Weak_ptr++].Si);
for(int i=B-1; ~i; i--)
{
int CanHave = X;
while(CanHave-- && !pq.empty() && pq.top() < Small[i])
pq.pop();
}
return pq.empty();
}
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++) Weak[i] = X[i];
for(int i=0; i<B; i++) Small[i] = Y[i];
for(int i=0; i<T; i++) WeTs[i] = {W[i] ,S[i]};
sort(Weak ,Weak+A);
sort(Small ,Small+B);
sort(WeTs ,WeTs+T);
int st = 1 ,en = T ,mid;
while(st <= en)
{
mid = (st+en)>>1;
if(can(mid))
en = mid-1;
else
st = mid+1;
}
return (en == T ? -1 : en+1);
}
