#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
#define rep(i , j , k) for (int i = j; i < (int)k; i++)
typedef pair<int , int> pii;
const int MAXN = 1e6 + 10;
int a[MAXN], w[MAXN], s[MAXN], x[MAXN], y[MAXN], fA , fB, t;
int arr[MAXN], rtp;
inline void push(int v) {
arr[++rtp] = v;
int id = rtp;
while (id > 1 && arr[id >> 1] < arr[id]) {
swap(arr[id] , arr[id >> 1]);
id >>= 1;
}
}
inline void pop() {
if (rtp == 1) return rtp = 0, void();
swap(arr[1] , arr[rtp--]);
int id = 1;
while (true) {
if ((id << 1) > rtp) return;
if ((id << 1) == rtp) {
if (arr[id] < arr[id << 1])
swap(arr[id] , arr[id << 1]);
return;
}
int me = id << 1;
if (arr[me] < arr[me + 1])
me++;
if (arr[id] < arr[me]) {
swap(arr[id] , arr[me]);
id = me;
}
else return;
}
}
inline bool check(int mid) {
rtp = 0;
int ptr = 0;
rep(i , 0 , fA) {
while (ptr < t && w[a[ptr]] < x[i])
push(s[a[ptr++]]);
rep(j , 0 , mid)
if (rtp)
pop();
}
while (ptr < t)
push(s[a[ptr++]]);
rep(i , 0 , fB)
rep(j , 0 , mid) {
if (rtp && arr[1] >= y[i]) return false;
if (rtp) pop();
}
return !rtp;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
fA = A, fB = B,t = T;
iota(a , a + T , 0);
rep(i , 0 , T) w[i] = W[i], s[i] = S[i];
rep(i , 0 , A) x[i] = X[i];
rep(i , 0 , B) y[i] = Y[i];
sort(a , a + T, [](int l , int r) { return pii(w[l] , -s[l]) < pii(w[r] , -s[r]); });
sort(x , x + A);
sort(y , y + B, greater<int>());
int lo = -1, hi = T + 1;
while (lo != hi - 1) {
int mid = lo + hi >> 1;
if (check(mid))
hi = mid;
else
lo = mid;
}
if (hi == T + 1) hi = -1;
return hi;
}
