#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int inf = 2e9 + 10;
const int maxn = 5e4 + 10;
const int maxt = 1e6 + 10;
int wbots[maxn], sbots[maxn];
struct Toy{
int w, s; Toy( int w = 0, int s = 0 ): w(w), s(s) {}
bool operator < ( Toy t ){ return (( s == t.s ) ? w > t.w : s > t.s ); }
} toys[maxt];
bool check( int A, int B, int T, int k ){
multiset<pair<int, int>> s;
for( int i = 0; i < A; i++ ) s.insert({ wbots[i] - 1, k });
ll cont = 0, i = 0;
for( int t = 0; t < T; t++ ){
Toy cur = toys[t];
for( i; i < B && sbots[i] > cur.s; i++ ) cont += k;
auto it = s.lower_bound({ cur.w, 0 });
if( it == s.end() ){
if( cont ){ cont--; continue; }
return false;
}
auto [val, qtd] = *it;
s.erase(it);
if( qtd > 1 ) s.insert({ val, qtd - 1 });
}
return true;
}
int bs( int A, int B, int T ){
int l = (T + A + B - 1)/( A + B ), r = T + 1;
while( l < r ){
int mid = ( l + r )/2;
if( check( A, B, T, mid ) ) r = mid;
else l = mid + 1;
}
return ( r == T + 1 ) ? -1 : r;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
for( int i = 0; i < A; i++ ) wbots[i] = X[i];
for( int i = 0; i < B; i++ ) sbots[i] = Y[i];
for( int i = 0; i < T; i++ ) toys[i] = Toy( W[i], S[i] );
sort( wbots, wbots + A );
sort( sbots, sbots + B, greater<int>() );
sort( toys, toys + T );
return bs( A, B, T );
}
