#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
int A, B, T;
vector<int> robotWT, robotSZ, toyWT, toySZ;
struct cmp {
bool operator()(const int a, const int b) const {
return toySZ[a] > toySZ[b];
}
};
vector<int> wt;
priority_queue<int, vector<int>, cmp> pq; // pq K largest toys
bool check(int M) {
while(pq.size()) pq.pop();
int i = 0, r = 0;
while(i < T && r < A) { // weak robots
if (toyWT[wt[i]] < robotWT[r]) pq.push(wt[i++]);
else {
int k = M;
while(k-- && pq.size()) {
pq.pop();
}
r++;
}
}
while(r < A) {
int k = M;
while(k-- && pq.size()) {
pq.pop();
}
r++;
}
while(i < T) pq.push(wt[i++]);
for(int r = 0; r < B; r++) {
int k = M;
while(pq.size() && k-- && toySZ[pq.top()] < robotSZ[r]) {
pq.pop();
}
}
return pq.empty();
}
int putaway(int a, int b, int t, int X[], int Y[], int W[], int S[]) {
A = a, B = b, T = t;
robotWT.resize(A), robotSZ.resize(B), toyWT.resize(T), toySZ.resize(T);
for(int i = 0; i < A; i++) robotWT[i] = X[i];
for(int i = 0; i < B; i++) robotSZ[i] = Y[i];
for(int i = 0; i < T; i++) toyWT[i] = W[i], toySZ[i] = S[i];
sort(robotWT.begin(), robotWT.end()), sort(robotSZ.begin(), robotSZ.end(), greater<>());
wt.resize(T);
iota(wt.begin(), wt.end(), 0);
sort(wt.begin(), wt.end(), [&](const int a, const int b) {return toyWT[a] < toyWT[b]; });
int l = 1, r = T+1;
while(l < r) {
int m = (l + r) / 2;
if (check(m)) r = m;
else l = m + 1;
}
return (l == T+1 ? -1 : l);
}
