#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
pair<int, int>toys[1000005];
bool ok(int freq, int a, int b, int t, int x[], int y[]) {
int p = 0;
priority_queue<int> s;
for (int i = 0; i < a; ++i) {
while (p < t && toys[p].first < x[i]) {
s.push(toys[p].second);
p++;
}
int aux = freq;
for (int aux = freq; aux && !s.empty(); --aux)
s.pop();
}
for (; p < t; ++p)
s.push(toys[p].second);
for (int i = b - 1; i >= 0 && !s.empty(); --i) {
for (int aux = freq; aux && !s.empty(); --aux) {
int vl = s.top();
s.pop();
if (vl >= y[i])
return 0;
}
}
if (s.empty())
return 1;
return 0;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
for (int i = 0; i < T; ++i)
toys[i] = {W[i], S[i]};
sort(X, X + A);
sort(Y, Y + B);
sort(toys, toys + T);
int l = 1, r = T, last = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (ok(mid, A, B, T, X, Y)) {
last = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return last;
}
/*int x[50005], y[50005], w[1000005], s[1000005];
int main() {
freopen("robots.in", "r", stdin);
freopen("robots.out", "w", stdout);
int A, B, T;
scanf("%d%d%d", &A, &B, &T);
for (int i = 0; i < A; ++i)
scanf("%d", &x[i]);
for (int i = 0; i < B; ++i)
scanf("%d", &y[i]);
for (int i = 0; i < T; ++i)
scanf("%d%d", &w[i], &s[i]);
printf("%d\n", putaway(A, B, T, x, y, w, s));
return 0;
}*/
