#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
bool good[1000006];
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
if (A != 0) {
sort(X, X + A);
}
vector<pair<int, int>> toy(T);
for (int i = 0; i < T; ++i) {
toy[i] = {W[i], S[i]};
}
sort(toy.begin(), toy.end());
int l = 1, r = T + 1;
if (B != 0) {
sort(Y, Y + B);
} else {
sort(W, W + T);
while (l < r) {
int mid = (l + r) >> 1;
int p = T - 1;
bool ok = true;
for (int i = A - 1; i >= 0 && p >= 0; --i) {
for (int j = 0; j < mid && p >= 0; ++j, --p) {
if (W[p] >= X[j]) {
ok = false;
break;
}
}
}
if (ok) r = mid;
else l = mid + 1;
}
return (l == T + 1 ? -1 : l);
}
while (l < r) {
int mid = (l + r) >> 1;
memset(good, 0, sizeof good);
multiset<int> se;
for (int i = B - 1; i >= 0 && (int) se.size() < T; --i) {
for (int j = 0; j < mid; ++j) {
se.insert(Y[i]);
if ((int) se.size() == T) {
break;
}
}
}
for (int i = T - 1; i >= 0; --i) {
auto it = se.upper_bound(toy[i].second);
if (it != se.end()) {
se.erase(it);
good[i] = true;
}
}
se.clear();
for (int i = A - 1; i >= 0 && (int) se.size() < T; --i) {
for (int j = 0; j < mid; ++j) {
se.insert(X[i]);
if ((int) se.size() == T) {
break;
}
}
}
for (int i = T - 1; i >= 0; --i) {
auto it = se.upper_bound(toy[i].first);
if (good[i]) continue;
if (it != se.end()) {
se.erase(it);
good[i] = true;
}
}
bool ok = true;
for (int i = 0; i < T; ++i) {
ok &= good[i];
}
if (ok) {
r = mid;
} else {
l = mid + 1;
}
}
return (l == T + 1 ? -1 : l);
}
