#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
typedef pair<int, int> pii;
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];
int kul[MAXN];
bool check(int d){
memset(done, 0, sizeof(done));
memset(kul, 0, sizeof(kul));
set<int> st;
for(int i = 0; i < b; i++){
st.insert(y[i]);
kul[y[i]] += d;
}
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;
kul[*u]--;
if(kul[*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 putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
a = A;
b = B;
x = X;
y = Y;
w = W;
s = S;
t = T;
sort(X, X + A);
sort(Y, Y + B);
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;
}
