#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
static int A, B, T;
static int robot1[50009], robot2[50009];
static pair<int,int> toys[1000009];
bool check(int lim) {
priority_queue<int> pq;
int pt = 1;
// phase 1: robots yếu
for (int i = 1; i <= A; i++) {
while (pt <= T && toys[pt].first <= robot1[i]) {
pq.push(toys[pt].second);
pt++;
}
for (int j = 1; j <= lim; j++) {
if (pq.empty()) break;
pq.pop();
}
}
// phase 2: gom toys còn lại
while (pt <= T) {
pq.push(toys[pt].second);
pt++;
}
vector<int> leftover;
while (!pq.empty()) {
leftover.push_back(pq.top());
pq.pop();
}
sort(leftover.begin(), leftover.end());
int idx = 0;
for (int i = 1; i <= B; i++) {
for (int j = 1; j <= lim; j++) {
if (idx < (int)leftover.size() && leftover[idx] <= robot2[i]) {
idx++;
} else break;
}
}
return idx == (int)leftover.size();
}
int putaway(int a, int b, int t, int X[], int Y[], int W[], int S[]) {
A = a;
B = b;
T = t;
for (int i = 1; i <= A; i++) robot1[i] = X[i-1];
for (int i = 1; i <= B; i++) robot2[i] = Y[i-1];
for (int i = 1; i <= T; i++) {
toys[i].first = W[i-1] + 1;
toys[i].second = S[i-1] + 1;
}
sort(robot1 + 1, robot1 + 1 + A);
sort(robot2 + 1, robot2 + 1 + B);
sort(toys + 1, toys + 1 + T);
int l = 1, r = T, ans = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
}
