#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int A, B, n, X[N], Y[N], W[N], S[N], I[N], ub[N];
int par[N], cnt[N];
int Find(int u){
if(par[u] == u) return u;
return par[u] = Find(par[u]);
}
bool Check(int x){
//cerr << "! " << x << '\n';
iota(par, par + A + 1, 0);
for(int i = 0; i <= A; i++) cnt[i] = x;
int nw = B - 1;
int hp = x;
for(int i = n - 1; i >= 0; i--){
int bot = Find(ub[i]);
if(bot < A){
cnt[bot] --;
if(cnt[bot] == 0) par[bot] = bot + 1;
continue;
}
while( (nw >= 0) && ((hp == 0) || (S[i] >= Y[nw])) ){
nw --;
hp = x;
}
if(nw == -1) return false;
hp --;
}
return true;
}
int putaway(int _A, int _B, int _n, int _X[], int _Y[], int _W[], int _S[]){
A = _A; B = _B; n = _n;
for(int i = 0; i < A; i++) X[i] = _X[i];
for(int i = 0; i < B; i++) Y[i] = _Y[i];
//for(int i = 0; i < n; i++) W[i] = _W[i];
//for(int i = 0; i < n; i++) S[i] = _S[i];
sort(X, X + A);
sort(Y, Y + B);
iota(I, I + n, 0);
sort(I, I + n, [&](int i, int j){
return _S[i] < _S[j];
});
for(int i = 0; i < n; i++) S[i] = _S[I[i]];
for(int i = 0; i < n; i++) W[i] = _W[I[i]];
for(int i = 0; i < n; i++)
ub[i] = upper_bound(X, X + A, W[i]) - X;
int up = n + 1;
int L = 0, R = up, mid;
while(L + 1 < R){
mid = (L + R) >> 1;
if(Check(mid))
R = mid;
else
L = mid;
//cerr << "# " << mid << '\n';
}
if(R == up) return -1;
return R;
}
