#include "bits/stdc++.h"
#include"robots.h"
#ifdef mlocal
#include "grader.c"
#endif
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
//#define endl '\n'
// Ask for sum 1 -> n for full (one based indexing)
class BIT {
private: vector<ll> tree; int n = 1e6;
int LSOne(int x) {
return x&(-x);
}
public:
void build(int x) {
n = x;
tree.resize(n+1);
}
ll sum(int a) {
ll sum = 0;
for (; a > 0; a -= LSOne(a)) sum += tree[a];
return sum;
}
ll sum(int a, int b) {
return sum(b) - (a == 1 ? 0 : sum(a-1));
}
void update(int p, ll v) {
for (; p < n+1; p += LSOne(p)) tree[p] += v;
}
};
int a, b, t;
vi wlim, slim;
vector<ii> toys, toys2;
BIT tree;
bool check(ll box) {
vi left, done;
for (int i = t-1; i >= 0; i--) {
int pt = lower_bound(slim.begin(), slim.end(), toys[i][1]) - slim.begin();
if (pt < b and tree.sum(pt+1, b) < box * (b-pt)) {
tree.update(pt+1, 1);
done.push_back(pt);
} else left.push_back(i);
}
for (auto &i: done) tree.update(i+1, -1);
done.clear();
bool valid = true;
for (auto i: left) {
int pt = lower_bound(wlim.begin(), wlim.end(), toys[i][0]) - wlim.begin();
if (pt < a and tree.sum(pt+1, a) < box * (a-pt)) {
tree.update(pt+1, 1);
done.push_back(pt);
} else {
valid = false;
break;
}
}
for (auto &i: done) tree.update(i+1, -1);
return valid;
}
bool checkk(ll box) {
bool valid = check(box);
if (!valid) {
swap(toys2, toys);
swap(a, b);
swap(wlim, slim);
valid |= check(box);
swap(toys2, toys);
swap(a, b);
swap(wlim, slim);
}
return valid;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
a = A, b = B, t = T;
wlim.reserve(A); slim.reserve(B); toys.reserve(T);
for_(i, 0, a) {
wlim.push_back(X[i]);
wlim[i] -= 1;
}
for_(i, 0, b) {
slim.push_back(Y[i]);
slim[i] -= 1;
}
for_(i, 0, t) toys.push_back({W[i], S[i]});
toys2 = toys;
for_(i, 0, t) swap(toys2[i][0], toys2[i][1]);
sort(wlim.begin(), wlim.end());
sort(slim.begin(), slim.end());
sort(toys.begin(), toys.end());
sort(toys2.begin(), toys2.end());
for_(i, 0, t) if ((a == 0 or toys[i][0] > wlim.back()) and (b == 0 or toys[i][1] > slim.back())) return -1;
tree.build(max(a, b));
int l = 0, r = T+1, ans = r;
while (l < r) {
int mid = (l+r)/2;
bool fin = checkk(mid);
if (fin) {
ans = r = mid;
} else l = mid+1;
}
return ans;
}
//#define MAX_A 50000
//#define MAX_B 50000
//#define MAX_T 500000
//#define fail(s, x...) do { \
// fprintf(stderr, s "\n", ## x); \
// exit(1); \
// } while(0)
//
//static int X[MAX_A];
//static int Y[MAX_B];
//static int W[MAX_T];
//static int S[MAX_T];
//
//int main() {
// int A, B, T, i;
// int res;
//
// FILE *f = fopen("test.in", "r");
// if (!f)
// fail("Failed to open input file.");
//
// res = fscanf(f, "%d", &A);
// if (res != 1)
// fail("Failed to read A from input file.");
// if (A < 0 || A > MAX_A)
// fail("A is out of bounds.");
//
// res = fscanf(f, "%d", &B);
// if (res != 1)
// fail("Failed to read B from input file.");
// if (B < 0 || B > MAX_B)
// fail("B is out of bounds.");
//
// res = fscanf(f, "%d", &T);
// if (res != 1)
// fail("Failed to read T from input file.");
// if (T < 1 || T > MAX_T)
// fail("T is out of bounds.");
//
// for (i = 0; i < A; i++) {
// res = fscanf(f, "%d", &X[i]);
// if (res != 1)
// fail("Failed to read data from input file.");
// }
// for (i = 0; i < B; i++) {
// res = fscanf(f, "%d", &Y[i]);
// if (res != 1)
// fail("Failed to read data from input file.");
// }
// for (i = 0; i < T; i++) {
// res = fscanf(f, "%d%d", &W[i], &S[i]);
// if (res != 2)
// fail("Failed to read data from input file.");
// }
// fclose(f);
//
// int answer = putaway(A, B, T, X, Y, W, S);
//
// printf("%d\n", answer);
//
// return 0;
//}
