#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
sort(X, X + A);
sort(Y, Y + B);
vector<pair<int, int>> p(T);
for (int i = 0; i < T; ++i) {
p[i] = make_pair(W[i], S[i]);
if ((!A || W[i] >= X[A - 1]) && (!B || S[i] >= Y[B - 1])) {
return -1;
}
}
sort(p.begin(), p.end());
auto check = [&](int t) {
vector<int> remain(B, t);
set<pair<int, int>> st;
for (int i = 0; i < B; ++i) {
st.insert(make_pair(Y[i], i));
}
long long free = 0;
int j = T - 1;
for (int i = A - 1; ~i; --i) {
while (~j && p[j].first >= X[i]) {
auto it = st.lower_bound(make_pair(p[j].second + 1, -1));
if (it == st.end()) {
if (!free) {
return false;
} else {
--free;
}
} else if (!--remain[it->second]) {
st.erase(it);
}
--j;
}
free += t;
}
while (~j) {
auto it = st.lower_bound(make_pair(p[j].second + 1, -1));
if (it == st.end()) {
if (!free) {
return false;
} else {
--free;
}
} else if (!--remain[it->second]) {
st.erase(it);
}
--j;
}
return true;
};
int l = 1, r = T;
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return r;
}
