#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
typedef long long ll;
const ll MAXT = 1e6 + 10;
const ll MAXA = 5e4 + 10;
const ll MAXB = 5e4 + 10;
struct toy
{
ll sz;
ll w;
toy(){};
toy(ll _w, ll _sz)
{
w = _w;
sz = _sz;
}
bool operator<(const toy&t)const
{
return sz < t.sz;
}
};
bool cmp(ll a, ll b)
{
return a > b;
}
ll t,a,b;
ll weak[MAXA];
ll small[MAXB];
toy toys[MAXT];
bool check(ll k)
{
priority_queue < toy > pq;
ll ptr = 0;
for(int i = 0; i < b; i++)
{
while(ptr < t && toys[ptr].sz < small[i])
{
pq.push(toys[ptr]);
ptr++;
}
for(int j = 1; j <= k; j++)
{
if(pq.empty())
break;
pq.pop();
}
}
while(ptr < t)
{
pq.push(toys[ptr]);
ptr++;
}
for(int i = 0; i < a; i++)
{
if(pq.empty())
break;
if(pq.top().w >= weak[i])
return false;
for(int j = 1; j <= k; j++)
{
if(pq.empty())
break;
pq.pop();
}
}
return pq.empty();
}
int solve()
{
ll left = 0;
ll right = t + 1;
ll mid;
while(left <= right)
{
mid = left + (right - left) / 2;
if(check(mid))
right = mid - 1;
else
left = mid + 1;
}
return right == t + 1 ? -1 : right;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
t = T;
a = A;
b = B;
for(int i = 0; i < t; i++)
{
toys[i] = toy(W[i], S[i]);
}
for(int i = 0; i < a; i++)
{
weak[i] = X[i];
}
for(int i = 0; i < b; i++)
{
small[i] = Y[i];
}
sort(toys, toys + t);
sort(weak, weak + a, cmp);
sort(small, small + b);
return solve();
}
