#include "robots.h"
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
struct toy
{
int w, s;
bool operator<(const toy &x) const
{
if (s != x.s)
return s < x.s;
return w < x.w;
}
};
bool cmp(toy x, toy y)
{
if (x.w != y.w)
return x.w < y.w;
return x.s < y.s;
}
const int MAXT = 1000010, MAXN = 50100;
toy toys[MAXT];
int a, b, t;
int x[MAXN], y[MAXN];
bool check(int mid)
{
priority_queue<toy> q;
int p = 1;
for (int i = 1; i <= a; i++)
{
while (p <= t && toys[p].w < x[i])
{
q.push(toys[p]);
p++;
}
int cnt = mid;
while (cnt > 0 && q.size())
{
cnt--;
q.pop();
}
}
while (p <= t)
{
q.push(toys[p]);
p++;
}
for (int i = 1; i <= b; i++)
{
int cnt = mid;
while (cnt > 0 && q.size() && q.top().s < y[i])
{
cnt--;
q.pop();
}
}
return q.empty();
}
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++)
{
x[i] = X[i-1];
}
sort(x + 1, x + 1 + a);
for (int i = 1; i <= b; i++)
{
y[i] = Y[i-1];
}
sort(y + 1, y + 1 + b);
reverse(y + 1, y + 1 + b);
for (int i = 1; i <= t; i++)
{
toys[i] = {W[i-1], S[i-1]};
}
sort(toys + 1, toys + 1 + t,cmp);
int ans = -1;
int l = 1;
int r = t;
while (l <= r)
{
int mid = (l + r) / 2;
if (check(mid))
{
ans = mid;
r = mid - 1;
}
else
{
l = mid + 1;
}
}
return ans;
}
