#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1 << 20;
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))
void compress (vector<int> &v) {
sort(all(v));
v.resize(unique(all(v)) - v.begin());
}
int A, B, N;
int *X, *Y, *W, *S;
pii T[MAXN];
bool moo (int g) {
if (g * ll(A + B) < N) {
return false;
}
priority_queue<int> pq;
//memory limit is so fucking strict...i don't even understand
//and then you need a TLE sol...wtf??
int ptr = 0;
for (int i = 0; i < A; i++) {
//insert stuff in
for (; ptr < N && T[ptr].fi < X[i]; ptr++) {
pq.push(T[ptr].se);
}
for (int taken = 0; !pq.empty() && taken < g; taken++) {
pq.pop();
}
}
for (; ptr < N; ptr++) {
pq.push(T[ptr].se);
}
//by now you don't even care about weight.
for (int i = B - 1; i >= 0; i--) {
//if ur stuck
if (!pq.empty() && pq.top() >= Y[i]) {
return false;
}
for (int taken = 0; !pq.empty() && taken < g; taken++) {
pq.pop();
}
}
return pq.empty();
}
int putaway (int aaa, int bbb, int nnn, int xxx[], int yyy[], int www[], int sss[]) {
A = aaa;
B = bbb;
N = nnn;
X = xxx;
Y = yyy;
W = www;
S = sss;
sort(X, X + A);
sort(Y, Y + B);
for (int i = 0; i < N; i++) {
if (W[i] >= X[A - 1] && S[i] >= Y[B - 1]) {
return -1;
}
T[i] = pii(W[i], S[i]);
}
sort(T, T + N);
//memory is the issue here
int lo = 0, hi = N;
while (hi - lo > 1) {
int mid = (lo + hi) / 2;
if (moo(mid)) {
hi = mid;
} else {
lo = mid;
}
}
return hi;
}
