#include "robots.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
#define all(V) ((V).begin()), ((V).end())
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;
typedef vector<ll> vlm;
vim cp1, cp2;
vector<pii> ar;
set<pii> S1, S2;
int cn1[50010], cn2[50010];
/*struct segTree {
int seg[(1<<18)];
void init() {memset(seg, 0, sizeof(seg));}
void upd(int t, int i, int fr, int re) {
if (!(fr<=t&&t<=re)) return ;
seg[i]++;
if (fr==re) return ;
int md=(fr+re)/2;
upd(t, i*2, fr, md);
upd(t, i*2+1, md+1, re);
}
int sum(int s, int e, int i, int fr, int re) {
if (fr>re) return 0;
if (s<=fr&&re<=e) return seg[i];
if (re<s||e<fr) return 0;
int md=(fr+re)/2;
return sum(s, e, i*2, fr, md)+sum(s, e, i*2+1, md+1, re);
}
}S1, S2;*/
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
for (int i=0; i<A; i++) cp1.push_back(X[i]);
for (int i=0; i<B; i++) cp2.push_back(Y[i]);
for (int i=0; i<T; i++) {cp1.push_back(W[i]); cp2.push_back(S[i]);}
sort(all(cp1)); cp1.erase(unique(all(cp1)), cp1.end());
sort(all(cp2)); cp2.erase(unique(all(cp2)), cp2.end());
for (int i=0; i<A; i++) X[i]=lower_bound(all(cp1), X[i])-cp1.begin();
for (int i=0; i<B; i++) Y[i]=lower_bound(all(cp2), Y[i])-cp2.begin();
for (int i=0; i<T; i++) {
W[i]=lower_bound(all(cp1), W[i])-cp1.begin();
S[i]=lower_bound(all(cp2), S[i])-cp2.begin();
}
sort(X, X+A); sort(Y, Y+B);
for (int i=0; i<T; i++) ar.push_back({W[i], S[i]});
sort(all(ar), [](pii x1, pii x2){return x1.fi==x2.fi?x1.se>x2.se:x1.fi>x2.fi;});
for (int i=0; i<T; i++) if (X[A-1]<=W[i]&&Y[B-1]<=S[i]) return -1;
int s=0, e=T;
set<pii>::iterator ub;
while (s+1<e) {
ll md=(s+e+1)/2;
int i;
for (i=0; i<A; i++) S1.insert({X[i], i});
for (i=0; i<B; i++) S2.insert({Y[i], i});
fill(cn1, cn1+A, md);
fill(cn2, cn2+B, md);
for (i=0; i<T; i++) {
ub=S2.upper_bound(make_pair(ar[i].se, A));
if (ub!=S2.end()) {
if (!(--cn2[(*ub).se])) S2.erase(ub);
}
else {
ub=S1.upper_bound(make_pair(ar[i].fi, B));
if (ub!=S1.end()) {
if (--cn1[(*ub).se]) S1.erase(ub);
}
else break;
}
}
if (i<T) s=md;
else e=md;
}
return e;
}
