#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;
struct segTree {
int seg[110000];
void init() {memset(seg, 0, sizeof(seg));}
void upd(int t, int i, int fr, int re) {
if (i>100000) return;
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 (i>100000)return 0;
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;
int ub;
while (s+1<e) {
ll md=(s+e+1)/2;
S1.init(); S2.init();
int i;
for (i=0; i<T; i++) {
ub=upper_bound(Y, Y+B, ar[i].se)-Y;
if (ub<B && (ll)S2.sum(ub, B, 1, 0, B)<md*(B-ub)) S2.upd(ub, 1, 0, B);
else {
ub=upper_bound(X, X+A, ar[i].fi)-X;
if (ub<A && (ll)S1.sum(ub, A, 1, 0, A)<md*(A-ub)) S1.upd(ub, 1, 0, A);
else break;
}
}
if (i<T) s=md;
else e=md;
}
return e;
}
