#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 sweepX[MAXN];
int sweepY[MAXN];
int szLimit[MAXN];
int weightLimit[MAXN];
bool picked[MAXN];
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 cmpSz(int i, int j) { return sz[i] < sz[j]; }
bool cmpWeight(int i, int j) { return weight[i] < weight[j]; }
bool test(int k)
{
int p = 1;
int qtdToys = 0;
set< pii > s;
vector< int > aux;
memset( picked , false , sizeof(picked) );
for(int i = 1 ; i <= qtdSmall ; i++)
{
while( p <= N && sz[ sweepX[p] ] < szLimit[i] )
{
int ind = sweepX[ p++ ];
s.insert( { -weight[ind] , ind } );
}
for(int j = 0 ; j < k ; j++)
{
if( s.empty() ) break;
int ind = s.begin()->second;
qtdToys++;
picked[ ind ] = true;
s.erase( s.begin() );
}
}
p = 1;
for(int i = 1 ; i <= qtdWeak ; i++)
{
while( p <= N && weight[ sweepY[p] ] < weightLimit[i] )
{
int ind = sweepY[ p++ ];
if( picked[ind] ) continue;
aux.push_back( ind );
}
for(int j = 0 ; j < k ; j++)
{
if( aux.empty() ) break;
qtdToys++;
picked[ aux.back() ] = true;
aux.pop_back();
}
}
return qtdToys == N;
}
int bs()
{
int l = 1;
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[i] = sweepY[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 + 1 , sweepX + N + 1 , cmpSz );
sort( sweepY + 1 , sweepY + N + 1 , cmpWeight );
sort( szLimit + 1 , szLimit + qtdSmall + 1 );
sort( weightLimit + 1 , weightLimit + qtdWeak + 1 );
return bs();
}
