#include "robots.h"
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
if(B == 0) {
sort(X, X+A);
int lo = 0, hi = 2*T;
int res=-1;
while(lo <= hi) {
bool check=1;
int mid = (lo+hi)/2;
vector<int> v(A);
for(int i = 0;i<T;i++) {
int it = upper_bound(X, X+A, W[i])-X;
if(it == A) {
check=0;
break;
}
v[it]++;
}
if(check) {
for(int i = 0;i<A-1;i++) {
if(v[i] > mid) {
v[i+1]+=v[i]-mid;
v[i]=mid;
}
}
}
if(v.back() > mid or !check) {
lo = mid+1;
}
else {
res=mid;
hi=mid-1;
}
}
return res;
}
else if(A == 0) {
sort(Y, Y+B);
int lo = 0, hi = 2*T;
int res=-1;
while(lo <= hi) {
bool check=1;
int mid = (lo+hi)/2;
vector<int> v(B);
for(int i = 0;i<T;i++) {
int it = upper_bound(Y, Y+B, S[i])-Y;
if(it == B) {
check=0;
break;
}
v[it]++;
}
if(check) {
for(int i = 0;i<B-1;i++) {
if(v[i] > mid) {
v[i+1]+=v[i]-mid;
v[i]=mid;
}
}
}
if(v.back() > mid or !check) {
lo = mid+1;
}
else {
res=mid;
hi=mid-1;
}
}
return res;
}
sort(X, X+A);
sort(Y, Y+B);
int lo = 0, hi = 2*T;
vector<int> v[A];
vector<int> vv;
while(hi-lo > 1) { // (lo,hi]
int mid = (lo+hi)/2, check=1;
priority_queue<int> pq;
vv.clear();
for(int i = 0;i<T;i++) {
int it = upper_bound(X, X+A, W[i])-X;
if(it == A)vv.push_back(S[i]);
else v[it].push_back(S[i]);
}
for(int i = 0;i<A;i++) {
int cnt = 0;
for(int j:v[i])pq.push(j);
while(cnt < mid and pq.size()) {
pq.pop();
cnt++;
}
v[i].clear();
}
for(int i:vv)pq.push(i);
for(int i = 0;i<B and pq.size();i++) {
int cnt = mid;
while(cnt-- and pq.size() && pq.top() < Y[i]){
pq.pop();
}
}
check&=pq.empty();
if(!check) {
lo = mid;
}
else {
hi = mid;
}
}
if(hi == 2*T)return -1;
return hi;
}
