#include "robots.h"
#include<queue>
#include<utility>
#include<algorithm>
#define MAXT 1000005
#define MAXR 50005
using namespace std;
pair<int,int> Toy[MAXT];
priority_queue<int> PQ; //from big to small
int A, B, T, Weak[MAXR], Small[MAXR]; //weak size, small size
bool can(int k) {
int pt = 0;
while (PQ.size()) {PQ.pop();}
for (int i=0; i<A; i++) {
while (pt < T && Toy[pt].first < Weak[i]) {
PQ.push(Toy[pt].second), pt++;
}
for (int j=0; j<k && PQ.size(); j++) {PQ.pop();}
}
for (int i=pt; i<T; i++) {
PQ.push(Toy[i].second);
}
for (int i=B-1; i>=0; i--) {
for (int j=0; j<k; j++) {
if (PQ.size() && PQ.top() < Small[i]) {PQ.pop();}
else {break;}
}
}
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; //weak num, small num, toy num
for (int i=0; i<T; i++) {
Toy[i].first = w[i];
Toy[i].second = s[i];
}
for (int i=0; i<a; i++) {
Weak[i]=x[i];
}
for (int i=0; i<b; i++) {
Small[i]=y[i];
}
sort(Weak, Weak+A);
sort(Small, Small+B);
sort(Toy, Toy+T);
for (int i=0; i<T; i++) {
if ((!A || Toy[i].first >= Weak[A-1]) && (!B || Toy[i].second >= Small[B-1])) {
return(-1);
}
}
int lo = 0, hi = T;
while (lo + 1 != hi) {
int mid = (lo + hi) >> 1;
if (can(mid)) {hi = mid;}
else {lo = mid;}
}
return(hi);
}
