#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);
long long lo = 0, hi = 2*T;
long long res=-1;
while(lo <= hi) {
bool check=1;
long long mid = (lo+hi)/2;
vector<long long> v(A);
for(long long i = 0;i<T;i++) {
long long it = upper_bound(X, X+A, W[i])-X;
if(it == A) {
check=0;
break;
}
v[it]++;
}
if(check) {
for(long long 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);
long long lo = 0, hi = 2*T;
long long res=-1;
while(lo <= hi) {
bool check=1;
long long mid = (lo+hi)/2;
vector<long long> v(B);
for(long long i = 0;i<T;i++) {
long long it = upper_bound(Y, Y+B, S[i])-Y;
if(it == B) {
check=0;
break;
}
v[it]++;
}
if(check) {
for(long long 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);
long long lo = 0, hi = 2*T;
while(hi-lo > 1) { // (lo,hi]
long long mid = (lo+hi)/2, check=1;
priority_queue<long long> pq;
vector<long long> vv;
vector<long long> v[A];
for(long long i = 0;i<T;i++) {
long long 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(long long i = 0;i<A;i++) {
long long cnt = 0;
for(long long j:v[i])pq.push(j);
while(cnt < mid and pq.size()) {
pq.pop();
cnt++;
}
}
for(long long i:vv)pq.push(i);
vector<long long> v2(B);
while(pq.size()) {
long long t = pq.top();
pq.pop();
long long idx=upper_bound(Y, Y+B, t)-Y;
if(idx==B){
check=0;
break;
}
v2[idx]++;
}
if(!check) {
lo = mid+1;
continue;
}
for(long long i = 0;i<B-1;i++) {
if(v2[i] > mid) {
v2[i+1]+=v2[i]-mid;
v2[i]=mid;
}
}
if(v2.back() > mid) {
lo = mid;
}
else {
hi = mid;
}
}
if(hi == 2*T)return -1;
return hi;
}
