#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1000 * 1000 + 5;
int n, m, p, a[N], b[N];
pair <int, int> c[N];
bool isval(int val) {
multiset <int> s;
int t = 0;
for (int i = 0; i < n; i++) {
while (c[t].first < a[i]) {
s.insert(c[t].second);
t++;
}
for (int j = 0; j < val; j++) {
if (s.size()) {
multiset <int> :: iterator it = s.end();
it--;
s.erase(it);
}
else {
break;
}
}
}
while (t < p) {
s.insert(c[t].second);
t++;
}
// cout << "72 " << val << " " << s.size() << endl;
// for (auto x : s) {
// cout << "71 " << x << endl;
/// }
for (int i = 0; i <= m; i++) {
// cout << "74 " << b[i] << endl;
for (int j = 0; j < val; j++) {
if (s.size()) {
if (*s.begin() < b[i]) {
s.erase(s.begin());
}
}
else {
return true;
}
}
}
// cout << "73 " << s.size() << endl;
if (s.empty()) {
return true;
}
return false;
}
int putaway(int NN, int M, int P, int A[], int B[], int W[], int S[]) {
n = NN, m = M, p = P;
sort(A, A + n);
sort(B, B + m);
int dw = 0, up = N;
for (int i = 0; i < n; i++) {
a[i] = A[i];
}
for (int i = 0; i < m; i++) {
b[i] = B[i];
}
for (int i = 0; i < p; i++) {
c[i] = {W[i], S[i]};
}
sort(c, c + p);
while (up - dw > 1) {
int md = (dw + up) / 2;
if (isval(md)) {
up = md;
}
else {
dw = md;
}
}
if (up == N) {
return -1;
}
return up;
}
