#include "robots.h"
#include "bits/stdc++.h"
using namespace std;
typedef pair <int, int> data;
data rob[1000010];
int weak[1000010];
int small[1000010];
int a, b;
int t;
bool good(int x) {
priority_queue <int> Q;
int pointer = 0;
for(int i = 0; i < a; i++) {
int cap = weak[i];
int take = 0;
while(pointer < t && rob[pointer].first < cap) {
Q.push(rob[pointer].second);
++pointer;
}
while(take < x && !Q.empty()) {
Q.pop();
++take;
}
}
for(int i = pointer; i < t; i++) {
Q.push(rob[i].second);
}
vector <int> v;
while(!Q.empty()) {
v.push_back(Q.top());
Q.pop();
}
reverse(v.begin(), v.end());
int size = v.size();
pointer = 0;
for(int i = 0; i < b; i++) {
int cap = small[i];
int take = 0;
while(take < x && pointer < size && v[pointer] < cap) {
++pointer;
++take;
}
}
return (pointer >= size);
}
int search(int b, int e) {
if(b == e) {
return good(b) ? b : -1;
}
int m = (b + e) >> 1;
if(good(m)) {
return search(b, m);
} else {
return search(m + 1, e);
}
}
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++) {
rob[i] = make_pair(W[i], S[i]);
}
sort(weak, weak + a);
sort(small, small + b);
sort(rob, rob + t);
return search(1, t);
}
