#include "robots.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
int a, b, *x, *y, *w, *s, t;
vector<int> vc;
const int MAXN = (int) 2e6 + 5;
const int MAXM = (int) 5e4 + 5;
bool done[MAXN];
int kal[MAXN];
bool check(int d){
memset(done, 0, sizeof(done));
memset(kal, 0, sizeof(kal));
set<int> st;
for(int i = 0; i < b; i++){
kal[y[i]] += d;
st.insert(y[i]);
}
for(int j = t - 1; j >= 0; j--){
int cur = vc[j];
auto u = st.upper_bound(s[cur]);
if(u == st.end())
continue;
else{
done[j] = 1;
kal[*u]--;
if(kal[*u] == 0) st.erase(u);
}
}
int pt2 = a - 1, used = d;
for(int j = t - 1; j >= 0; j--){
if(done[j]) continue;
int cur = vc[j];
if(pt2 == -1 || x[pt2] <= w[cur]) return 0;
used--;
if(used == 0){
pt2--;
used = d;
}
}
return 1;
}
int ali[2];
map<int, int> mp;
set<int> st;
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
if(B > A){
swap(X, Y);
swap(W, S);
swap(A, B);
}
a = A;
b = B;
x = X;
y = Y;
w = W;
s = S;
t = T;
for(int i = 0; i < T; i++) st.insert(S[i]);
for(int i = 0; i < B; i++) st.insert(Y[i]);
int cnt = 1;
for(int i: st){
mp[i] = cnt++;
}
for(int i = 0; i < T; i++) S[i] = mp[S[i]];
for(int i = 0; i < B; i++) Y[i] = mp[Y[i]];
sort(X, X + A);
sort(Y, Y + B);
//cout<<ali[0]<<endl;
for(int i = 0; i < T; i++) vc.push_back(i);
sort(vc.begin(), vc.end(), [W](int a, int b){
return W[a] < W[b];
});
for(int j = vc.size() - 1; j >= 0; j--){
if(W[vc[j]] < X[A - 1]) break;
if(S[vc[j]] >= Y[B - 1]) return -1;
}
int l = 1, r = T;
while(l < r){
int m = (l + r) / 2;
if(check(m)){
r = m;
}else{
l = m + 1;
}
}
return l;
}
