#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) 1e6 + 5;
const int MAXM = (int) 5e4 + 5;
bool done[MAXN];
struct pii{
mutable int ff, ss;
bool operator < (pii other) const{
return ff < other.ff;
}
};
bool check(int d){
memset(done, 0, sizeof(done));
multiset<pii> st;
for(int i = 0; i < b; i++){
st.insert({y[i], d});
}
for(int j = t - 1; j >= 0; j--){
int cur = vc[j];
auto u = st.upper_bound({s[cur], 0});
if(u == st.end())
continue;
else{
done[j] = 1;
(*u).ss--;
if((*u).ss == 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];
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;
sort(X, X + A);
sort(Y, Y + B);
memset(ali, 0x7f, sizeof(ali));
//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;
}
