#include "robots.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef gp_hash_table<int, null_type,hash<int>, equal_to<int>, direct_mask_range_hashing<int>, linear_probe_fn<>,
hash_standard_resize_policy<hash_exponential_size_policy<>, hash_load_check_resize_trigger<true>,true>> hash_set;
typedef gp_hash_table<int,null_type> hash_map;
#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;
#define complete_unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define all(a) a.begin(),a.end()
#define println printf("\n");
#define readln(x) getline(cin,x);
#define pb push_back
#define endl "\n"
#define INT_INF 0x3f3f3f3f
#define LL_INF 0x3f3f3f3f3f3f3f3f
#define EPS 1e-9
#define MOD 1000000007
#define MOD2 1494318097
#define SEED 131
#define mp make_pair
#define fastio cin.tie(0); cin.sync_with_stdio(0);
#define MAXN 50005
#define MAXT 1000005
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef pair<int,pii> triple;
typedef int8_t byte;
const ld PI = (ld)4*atanl(1);
mt19937 g1(chrono::steady_clock::now().time_since_epoch().count());
int randint(int a, int b){return uniform_int_distribution<int>(a, b)(g1);}
ll randlong(ll a,ll b){return uniform_int_distribution<long long>(a, b)(g1);}
ll gcd(ll a, ll b){return b == 0 ? a : gcd(b, a % b);}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
ll fpow(ll b, ll exp, ll mod){if(exp == 0) return 1;ll t = fpow(b,exp/2,mod);if(exp&1) return t*t%mod*b%mod;return t*t%mod;}
ll divmod(ll i, ll j, ll mod){i%=mod,j%=mod;return i*fpow(j,mod-2,mod)%mod;}
int num_weak,num_small,num_toys;
int weak[MAXN],small[MAXN];
bool done[MAXT];
pii arr[MAXT];
set<pii> s;
inline bool cmp(pii a, pii b){
if(a.first == b.first) return a.second>b.second;
return a.first<b.first;
}
inline bool works(int mid){
memset(done,false,sizeof done);
s.clear();
for(int i=1; i<=num_weak; i++)
s.insert(mp(weak[i],mid));
for(int i=num_toys; i>=1; i--){
auto it = s.upper_bound(mp(arr[i].second,INT_MAX));
if(it == s.end()) continue;
done[i] = true;
pii t = *it;
s.erase(t);
if(t.second > 1)
s.insert(mp(t.first,t.second-1));
}
int ptr = num_toys;
for(int i=num_small; i>=1; i--){
for(int k=1; k<=mid; k++){
while(ptr >= 1 && done[ptr]) ptr--;
if(ptr == 0) return true;
if(arr[ptr].first >= small[i]) return false;
ptr--;
}
}
while(ptr >= 1 && done[ptr]) ptr--;
return ptr==0;
}
inline bool can(int mid){
if(works(mid)) return true;
swap(num_small,num_weak);
swap(small,weak);
for(int i=1; i<=num_toys; i++)
swap(arr[i].first,arr[i].second);
return works(mid);
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]){
num_weak = A, num_small = B, num_toys = T;
for(int i=1; i<=A; i++) weak[i] = X[i-1];
for(int i=1; i<=B; i++) small[i] = Y[i-1];
sort(weak+1,weak+num_weak+1);
sort(small+1,small+num_small+1);
for(int i=1; i<=num_toys; i++){
arr[i].second = W[i-1], arr[i].first = S[i-1];
if(arr[i].second >= weak[num_weak] && arr[i].first >= small[num_small])
return -1;
}
sort(arr+1,arr+num_toys+1,cmp);
int low = 0, high = num_toys, ans = num_toys;
while(low <= high){
int mid = (low+high)/2;
if(can(mid)){
ans = mid;
high = mid-1;
}else low = mid+1;
}
return ans;
}
