#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define ll long long
vector<pii> els;
vector<int> rB;
vector<int> pos;
int n, a, b;
bool check(int x)
{
vector<int> can(n);
priority_queue<int> cur, els2;
ll canBeDeleted = 0, extra = 0;
for (int i = n - 1; i >= 0; --i)
{
cur.push(-els[i].s);
canBeDeleted += 1LL * pos[i] * x;
if (n - i > canBeDeleted + extra)
{
extra++;
els2.push(-cur.top());
cur.pop();
}
assert(cur.size() <= canBeDeleted);
}
for (int i = 0; i < b; ++i)
{
if (!els2.size())
break;
if (els2.top() >= rB[i])
return 0;
for (int j = 0; j < x; ++j)
{
if (els2.size() == 0)
break;
els2.pop();
}
}
return els2.size() == 0;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
n = T;
a = A;
b = B;
int L = 0, R = n + 1;
for (int i = 0; i < B; ++i)
{
rB.pb(Y[i]);
}
sort(all(rB));
reverse(all(rB));
for (int i = 0; i < n; ++i)
{
els.pb({W[i], S[i]});
}
sort(all(els));
pos.resize(n);
for (int i = 0; i < a; ++i)
{
auto it = lower_bound(all(els), make_pair(X[i], 0)) - els.begin();
if (it)
pos[it - 1]++;
}
while (R - L > 1)
{
int M = (L + R) >> 1;
if (check(M))
R = M;
else
L = M;
}
if (R == n + 1)
return -1;
else
return R;
}
// /////////////////
// #include <stdio.h>
// #include <stdlib.h>
// #include <assert.h>
// #include "robots.h"
// #define MAX_A 50000
// #define MAX_B 50000
// #define MAX_T 500000
// static int X[MAX_A];
// static int Y[MAX_B];
// static int W[MAX_T];
// static int S[MAX_T];
// int main()
// {
// int A, B, T, i;
// assert(scanf("%d", &A) == 1);
// assert(scanf("%d", &B) == 1);
// assert(scanf("%d", &T) == 1);
// for (i = 0; i < A; i++)
// assert(scanf("%d", &X[i]) == 1);
// for (i = 0; i < B; i++)
// assert(scanf("%d", &Y[i]) == 1);
// for (i = 0; i < T; i++)
// assert(scanf("%d%d", &W[i], &S[i]) == 2);
// int answer = putaway(A, B, T, X, Y, W, S);
// printf("%d\n", answer);
// return 0;
// }
