#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int MAXN = 1000010;
int N;
int qtdWeak;
int qtdSmall;
int sz[MAXN];
int weight[MAXN];
int szLimit[MAXN];
int weightLimit[MAXN];
bool picked[MAXN];
vector< pii > sweepX;
vector< pii > sweepY;
bool cmp(pii a, pii b)
{
int indA = a.second;
int indB = b.second;
if( a.first != b.first ) return a.first < b.first;
return weight[indA] + sz[indA] < weight[indB] + sz[indB];
}
bool test(int k)
{
int p = 0;
set< pii > s;
vector< int > aux;
memset( picked , false , sizeof(picked) );
for(int i = 1 ; i <= qtdSmall ; i++)
{
while( p < N && sweepX[p].first < szLimit[i] )
{
int ind = sweepX[ p++ ].second;
s.insert( { -weight[ind] , ind } );
}
for(int j = 0 ; j < k ; j++)
{
if( s.empty() ) break;
int ind = s.begin()->second;
picked[ ind ] = true;
s.erase( s.begin() );
}
}
p = 0;
for(int i = 1 ; i <= qtdWeak ; i++)
{
while( p < N && sweepY[p].first < weightLimit[i] )
{
int ind = sweepY[ p++ ].second;
if( picked[ind] ) continue;
aux.push_back( ind );
}
for(int j = 0 ; j < k ; j++)
{
if( aux.empty() ) break;
picked[ aux.back() ] = true;
aux.pop_back();
}
}
for(int i = 1 ; i <= N ; i++)
if( !picked[i] ) return false;
return true;
}
int bs()
{
int l = 0;
int r = N;
if( !test( r ) ) return -1;
while( l < r )
{
int m = ( l + r )/2;
if( test( m ) ) r = m;
else l = m + 1;
}
return r;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
N = T;
qtdWeak = A;
qtdSmall = B;
for(int i = 1 ; i <= N ; i++)
{
sz[i] = S[i - 1];
weight[i] = W[i - 1];
sweepX.push_back( { sz[i] , i } );
sweepY.push_back( { weight[i] , i } );
}
for(int i = 1 ; i <= qtdWeak ; i++)
weightLimit[i] = X[i - 1];
for(int i = 1 ; i <= qtdSmall ; i++)
szLimit[i] = Y[i - 1];
sort( sweepX.begin() , sweepX.end() , cmp );
sort( sweepY.begin() , sweepY.end() , cmp );
sort( szLimit + 1 , szLimit + qtdSmall + 1 );
sort( weightLimit + 1 , weightLimit + qtdWeak + 1 );
return bs();
}
