#include "robots.h"
#include<bits/stdc++.h>
#define lli int
using namespace std;
const lli MAXN=1000005, INF=999999999;
lli tree[4*MAXN], X[MAXN], Y[MAXN], S[MAXN], W[MAXN], A, B, T;
bool used[MAXN];
struct rob{
lli w, s, ind;
const bool operator <(rob p){
if(s!=p.s)return s>p.s;
if(w!=p.w)return w<p.w;
return ind<p.ind;
}
};
rob a[MAXN];
void build_tree(lli ind, lli l, lli r){
if(l==r){
tree[ind]=a[l].w;
return;
}
lli mid=(l+r)/2;
build_tree(2*ind, l, mid);
build_tree(2*ind+1, mid+1, r);
tree[ind]=min(tree[2*ind], tree[2*ind+1]);
return;
}
void update(lli ind, lli l, lli r, lli q, lli d){
if(l>q or r<q)return;
if(l==r){
tree[ind]=d;
used[l]=1;
return;
}
lli mid=(l+r)/2;
update(2*ind, l, mid, q, d);
update(2*ind+1, mid+1, r, q, d);
tree[ind]=min(tree[2*ind], tree[2*ind+1]);
return;
}
int query(lli ind, lli l, lli r, lli q){
if(l==r)return l;
lli mid=(l+r)/2;
if(tree[2*ind]<q)return query(2*ind, l, mid, q);
return query(2*ind+1, mid+1, r, q);
}
bool check(lli br){
build_tree(1, 0, T-1);
memset(used, 0, sizeof(used));
for(lli i=0; i<A; i++){
lli t=0;
while(t<br){
lli ind=query(1, 0, T-1, X[i]);
if(a[ind].w>=X[i])break;
update(1, 0, T-1, ind, INF);
t++;
}
}
lli p1=T-1;
for(lli i=0; i<B; i++){
lli t=0;
while(t<br){
while(used[p1]==1 and p1>=0)p1--;
if(p1<0 or a[p1].s>=Y[i])break;
p1--;
t++;
}
}
while(used[p1]==1 and p1>=0)p1--;
if(p1>=0)return 0;
return 1;
}
int bin_search(lli l, lli r){
while(l<r-1){
lli mid=(l+r)/2;
if(check(mid))r=mid;
else l=mid;
}
if(check(l))return l;
if(check(r))return r;
return -1;
}
int putaway(int A1, int B1, int T1, int X1[], int Y1[], int W1[], int S1[]) {
A=A1;
B=B1;
T=T1;
for(lli i=0; i<T; i++){
W[i]=W1[i];
S[i]=S1[i];
a[i]={W[i], S[i], i};
}
for(lli i=0; i<A; i++)X[i]=X1[i];
for(lli i=0; i<B; i++)Y[i]=Y1[i];
sort(a, a+T);
sort(X, X+A);
sort(Y, Y+B);
return bin_search(T/(A+B)+1, T);
}
