#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#include "robots.h"
#define pii pair<int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vvi vector<vi>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define f first
#define s second
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define size(v) (int)v.size()
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
bool check(int A, int B, int T, int H, int X[], int Y[], int W[], int S[]) {
int k = 0;
multiset<int>Ss;
for (int i = 0; i < A; ++i) {
while (k < T && W[k] < X[i]) {
Ss.insert(S[k]);
++k;
}
for (int j = 0; j < H && !Ss.empty(); ++j) {
Ss.erase(Ss.begin());
}
}
while(k < T) {
Ss.insert(S[k]);
++k;
}
for (int i = 0; i < B && !Ss.empty() && -(*Ss.begin()) < Y[i]; ++i) {
for (int j = 0; j < H && !Ss.empty(); ++j) {
Ss.erase(Ss.begin());
}
}
return Ss.empty();
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
sort(X, X + A);
sort(Y, Y + B);
reverse(Y, Y + B);
vector<pii>toys(T);
for (int i = 0; i < T; ++i) {
toys[i] = mpr(W[i], -S[i]);
}
sort(all(toys));
for (int i = 0; i < T; ++i) {
W[i] = toys[i].f;
S[i] = toys[i].s;
}
int l = 1, r = T + 1;
int mid;
while (l < r) {
mid = (l + r) >> 1;
if (check(A, B, T, mid, X, Y, W, S)) {
r = mid;
} else {
l = mid + 1;
}
}
if (r == T + 1) r = -1;
return r;
}
