#include "robots.h"
#include <bits/stdc++.h>
const int MAX_N = 1e6 + 42;
std::pair<int, int> toys[MAX_N];
int small[MAX_N];
int weak[MAX_N];
int a, b, t;
bool f( int x ){
// std::cerr<<" ! "<<x<<"\n";
std::priority_queue<int> q;
int ind = -1;
for( int i=0 ; i<a ; i++ ){
while( toys[ind+1].first < weak[i] ){
q.push(toys[ind+1].second);
ind++;
}
int num = x;
while( !q.empty() and num ){
num--;
q.pop();
}
}
// std::cerr<<" 1\n";
while( ind+1 < t ){
q.push( toys[ind+1].second );
ind++;
}
// std::cerr<<"2\n";
for( int i = b-1 ; i>=0 ; i-- ){
if( q.empty() ) return true;
int num = x;
while( !q.empty() and num ){
if( q.top() >= small[i] ) return false;
q.pop();
num--;
}
}
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=0 ; i<a; i++ ) weak[i] = X[i];
for( int i=0 ; i<b; i++ ) small[i] = Y[i];
for( int i=0 ; i<t ; i++ ) toys[i] = {W[i], S[i]};
std::sort( weak, weak + a );
std::sort( small, small + b );
std::sort( toys, toys + t );
int l = 0, r = t;
while( l != r-1 ){
int m = ( l + r ) >> 1;
if( f( m ) ) r = m;
else l = m;
}
if( !f(r) ) return -1;
return r;
}
