#include "robots.h"
#pragma GCC optimize("-O3")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define p_b pop_back
#define f first
#define s second
using namespace std;
using namespace __gnu_pbds;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
int i, j;
if(!B)
{
int maxx = 0;
for(i = 0; i < T; i++)
maxx = max(maxx, W[i]);
int mx = 0;
for(i = 0; i < A; i++)
mx = max(mx, X[i]);
if(mx <= maxx)
return -1;
vl vect1, vect2;
for(i = 0; i < T; i++)
vect1.pb(W[i]);
vect1.pb(LLONG_MAX);
sort(all(vect1));
for(i = 0; i < A; i++)
vect2.pb(X[i]);
sort(all(vect2));
priority_queue<pii>pq;
i = 0, j = 0;
vl idx[T+5];
while(i < (int)(vect2.size()) && j < (int)(vect1.size()-1))
{
if(vect2[i] <= vect1[j])
i++;
else if(vect2[i] > vect1[j] && vect2[i] <= vect1[j+1])
{
idx[j].pb(vect2[i]);
i++;
}
else
j++;
}
for(i = T - 1; i >= 0; i--)
{
for(auto u : idx[i])
pq.push({0, u});
ll a = pq.top().f, b = pq.top().s;
pq.pop();
a = -a;
a++;
pq.push({-a, b});
}
maxx = 0;
while(!pq.empty())
{
maxx = max(maxx, -pq.top().f);
pq.pop();
}
return maxx;
}
if(!A)
{
int maxx = 0;
for(i = 0; i < T; i++)
maxx = max(maxx, S[i]);
int mx = 0;
for(i = 0; i < B; i++)
mx = max(mx, Y[i]);
if(mx <= maxx)
return -1;
vl vect1, vect2;
for(i = 0; i < T; i++)
vect1.pb(S[i]);
vect1.pb(LLONG_MAX);
sort(all(vect1));
for(i = 0; i < B; i++)
vect2.pb(Y[i]);
sort(all(vect2));
priority_queue<pii>pq;
i = 0, j = 0;
vl idx[T+5];
while(i < (int)(vect2.size()) && j < (int)(vect1.size()-1))
{
if(vect2[i] <= vect1[j])
i++;
else if(vect2[i] > vect1[j] && vect2[i] <= vect1[j+1])
{
idx[j].pb(vect2[i]);
i++;
}
else
j++;
}
for(i = T - 1; i >= 0; i--)
{
for(auto u : idx[i])
pq.push({0, u});
ll a = pq.top().f, b = pq.top().s;
pq.pop();
a = -a;
a++;
pq.push({-a, b});
}
maxx = 0;
while(!pq.empty())
{
maxx = max(maxx, -pq.top().f);
pq.pop();
}
return maxx;
}
int n = T;
int w[n+5], s[n+5];
int a = A, b = B;
int x[a+5], y[b+5];
for(i = 1; i <= n; i++)
{
w[i] = W[i-1];
s[i] = S[i-1];
}
vl v1;
for(i = 1; i <= a; i++)
x[i] = X[i-1];
for(i = 1; i <= b; i++)
y[i] = Y[i-1];
vector<pair<pll, ll>>vect1;
for(i = 1; i <= n; i++)
vect1.pb({{s[i], w[i]}, i});
sort(rall(vect1));
int l = 1, r = n+1, res = n+1;
int mp[a+5], mp2[b+5];
while(l <= r){
int mid = (l + r) / 2;
set<pii>stt, stt2;
set<int>st;
for(i = 1; i <= a; i++){
stt.insert({x[i], i});
mp[i] = 0;
}
for(i = 1; i <= b; i++){
stt2.insert({y[i], i});
mp2[i] = 0;
}
stt.insert({INT_MAX, a+1});
stt2.insert({INT_MAX, b+1});
for(i = 0; i < vect1.size(); i++)
{
auto iter = stt.lower_bound({vect1[i].f.s+1, 0});
if((*iter).f == INT_MAX)
continue;
int idx = (*iter).s;
mp[idx]++;
st.insert(vect1[i].s);
if(mp[idx] == mid)
stt.erase(iter);
}
vector<pair<pll, ll>>vect;
for(i = 1; i <= n; i++)
{
if(!st.count(i))
vect.pb({{w[i], s[i]}, i});
}
for(i = 0; i < vect.size(); i++)
{
auto iter = stt2.lower_bound({vect[i].f.s+1, 0});
if((*iter).f == INT_MAX)
continue;
int idx = (*iter).s;
mp2[idx]++;
st.insert(vect[i].s);
if(mp2[idx] == mid)
stt2.erase(iter);
}
int sz = (int)(st.size());
if(sz == n)
{
res = mid;
r = mid - 1;
}
else
l = mid + 1;
}
if(res == n+1)
return -1;
return res;
}
/*int main()
{
int A, B, T;
cin >> T >> A >> B;
int X[A], Y[B], W[T], S[T];
for(int i = 0; i < T; i++)
cin >> W[i];
for(int i = 0; i < T; i++)
cin >> S[i];
for(int i = 0; i < A; i++)
cin >> X[i];
for(int i = 0; i < B; i++)
cin >> Y[i];
cout << putaway(A, B, T, X, Y, W, S) << "\n";
}
*/
