#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
int solve(int m, vector<int> &WR, vector<int> &SR, vector<pair<int, int>> &Tab)
{
int N = Tab.size();
vector<int> occ(N);
int buff = N - 1;
for (int i = WR.size() - 1; i >= 0; i--)
{
int left = m;
while (buff >= 0 && Tab[buff].first >= WR[i])
buff--;
while (left && buff >= 0)
{
occ[buff] = 1;
left--;
buff--;
}
}
priority_queue<int> PQ;
vector<int> remain;
for (int i = N - 1; i >= 0; i--)
{
PQ.push(-Tab[i].second);
if (occ[i] == 0)
{
remain.push_back(-PQ.top());
PQ.pop();
}
}
sort(remain.begin(), remain.end());
buff = remain.size() - 1;
for (int i = SR.size() - 1; i >= 0; i--)
{
int left = m;
if (buff >= 0 && remain[buff] >= SR[i])
return 0;
while (left && buff >= 0)
{
buff--;
left--;
}
}
return 1;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
vector<int> WR(A), SR(B);
for (int i = 0; i < A; i++)
WR[i] = X[i];
for (int i = 0; i < B; i++)
SR[i] = Y[i];
sort(WR.begin(), WR.end());
sort(SR.begin(), SR.end());
vector<pair<int, int>> Tab;
for (int i = 0; i < T; i++)
{
Tab.push_back({W[i], S[i]});
}
sort(Tab.begin(), Tab.end());
int L = 1, R = T + 1;
while (L != R)
{
int m = (L + R) / 2;
if (solve(m, WR, SR, Tab))
R = m;
else
L = m + 1;
}
if (L == T + 1)
return -1;
return L;
}
/*int main()
{
int A, B, T;
cin >> A >> B >> T;
int X[A], Y[B], W[T], S[T];
for (int i = 0; i < A; i++)
cin >> X[i];
for (int i = 0; i < B; i++)
cin >> Y[i];
for (int i = 0; i < T; i++)
cin >> W[i] >> S[i];
cout << putaway(A, B, T, X, Y, W, S);
}*/
