#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e6 + 20;
const int maxB = 5e4 + 20;
pair<int, int> W[maxN];
pair<int, int> S[maxN];
pair<int, int> cnt[maxN];
long long tree[maxB * 4];
int lazy[maxB * 4];
int A, B, N, K;
void build(int id, int lt, int rt) {
lazy[id] = 0;
if (lt == rt) {
tree[id] = -1LL * lt * K;
return;
}
int mt = (lt + rt) >> 1;
build(id << 1, lt, mt);
build(id << 1 | 1, mt + 1, rt);
tree[id] = max(tree[id << 1], tree[id << 1 | 1]);
}
void update(int id, int lt, int rt, int ql, int qr) {
if (lt == ql && rt == qr) {
tree[id]++;
lazy[id]++;
return;
}
tree[id << 1] += lazy[id];
lazy[id << 1] += lazy[id];
tree[id << 1 | 1] += lazy[id];
lazy[id << 1 | 1] += lazy[id];
lazy[id] = 0;
int mt = (lt + rt) >> 1;
if (qr <= mt) {
update(id << 1, lt, mt, ql, qr);
}
else if (ql >= mt + 1) {
update(id << 1 | 1, mt + 1, rt, ql, qr);
}
else {
update(id << 1, lt, mt, ql, mt);
update(id << 1 | 1, mt + 1, rt, mt + 1, qr);
}
tree[id] = max(tree[id << 1], tree[id << 1 | 1]);
}
bool check(int _K) {
K = _K;
build(1, 0, B);
for (int i = 0; i < N; i++) {
update(1, 0, B, cnt[i].second, B);
if (tree[1] > 1LL * cnt[i].first * K) {
return false;
}
}
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 < N; i++) {
W[i].first = _W[i];
W[i].second = i;
}
for (int i = 0; i < N; i++) {
S[i].first = _S[i];
S[i].second = i;
}
sort(W, W + N, greater<pair<int, int>>());
sort(S, S + N, greater<pair<int, int>>());
sort(X, X + A, greater<int>());
sort(Y, Y + B, greater<int>());
int lt = -1;
for (int i = 0; i < N; i++) {
while (lt < N - 1 && X[lt + 1] > W[i].first) {
lt++;
}
cnt[W[i].second].first = lt + 1;
}
lt = -1;
for (int i = 0; i < N; i++) {
while (lt < N - 1 && Y[lt + 1] > S[i].first) {
lt++;
}
cnt[S[i].second].second = lt + 1;
}
if (A < B) {
for (int i = 0; i < N; i++) {
swap(cnt[i].first, cnt[i].second);
}
swap(A, B);
}
sort(cnt, cnt + N);
lt = 1;
int rt = N;
int res = -1;
while (lt <= rt) {
int mt = (lt + rt) >> 1;
if (check(mt)) {
res = mt;
rt = mt - 1;
}
else {
lt = mt + 1;
}
}
return res;
}
