#include <bits/stdc++.h>
#include "robots.h"
struct Elem{
int val;
bool operator < (const Elem &aux) const{
return val > aux.val;
}
};
std::vector <int> Z;
std::priority_queue <Elem> pq;
int f(int lim, int A, int B, int T, int X[], int Y[], std::pair <int, int> V[]){
Z.clear();
while(!pq.empty()) pq.pop();
int pos = 0;
while(pos < T && V[pos].first > X[0]) Z.push_back(pos), pos++;
for(int i = 0; i < A; i++){
while(pos < T && (i == A - 1 || V[pos].first > X[i + 1]))
pq.push({pos}), pos++;
while(pq.size() > (i + 1) * lim){
Z.push_back(pq.top().val);
pq.pop();
}
}
std::sort(Z.begin(), Z.end());
std::reverse(Z.begin(), Z.end());
pos = 0;
if(Z[pos] < Z.size() && V[Z[pos]].second > Y[0]) return 0;
for(int i = 0; i < B; i++){
while(pos < Z.size() && (i == B - 1 || V[Z[pos]].second > Y[i + 1]))
pos++;
if(pos > (i + 1) * lim) return 0;
}
return 1;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]){
std::sort(X, X + A), std::reverse(X, X + A);
std::sort(Y, Y + B), std::reverse(Y, Y + B);
std::pair <int, int> V[T];
for(int i = 0; i < T; i++)
V[i] = {W[i], S[i]};
std::sort(V, V + T);
std::reverse(V, V + T);
if(!f(T, A, B, T, X, Y, V)) return -1;
int l = 1, r = T;
while(r - l > 1){
int m = (l + r) / 2;
if(f(m, A, B, T, X, Y, V)) r = m;
else l = m + 1;
}
if(f(l, A, B, T, X, Y, V)) return l;
return r;
}
/*
#define MAXA 50000
#define MAXB 50000
#define MAXT 1000000
int main(){
FILE*fi,*fo;
fi = fopen("a.in","r");
fo = fopen("a.out","w");
int A, B, T;
fscanf(fi,"%d%d%d", &A, &B, &T);
int X[MAXA], Y[MAXB], W[MAXT], S[MAXT];
for(int i = 0; i < A; i++) fscanf(fi,"%d", &X[i]);
for(int i = 0; i < B; i++) fscanf(fi,"%d", &Y[i]);
for(int i = 0; i < T; i++) fscanf(fi,"%d%d", &W[i], &S[i]);
fprintf(fo,"%d", putaway(A, B, T, X, Y, W, S));
return 0;
}*/
