#include "robots.h"
#include<bits/stdc++.h>
using namespace std;
struct in
{
int w, s, idx;
in() {}
in(int v1, int v2, int v3) : w(v1), s(v2), idx(v3) {}
};
bool cmp1(const in &lhs, const in &rhs){ return lhs.w==rhs.w ? lhs.s>rhs.s : lhs.w<rhs.w; }
bool cmp2(const in &lhs, const in &rhs){ return lhs.s==rhs.s ? lhs.w>rhs.w : lhs.s<rhs.s; }
bool operator < (in lhs, in rhs)
{
return lhs.s<rhs.s;
}
int cx[50005], cy[50005];
bool check[50005];
vector<in> arr1, arr2;
bool pos(int limit, int A, int B, int T, int X[], int Y[])
{
int idx=0, tot=T;
memset(cx,0,sizeof(cx));
memset(cy,0,sizeof(cy));
memset(check,false,sizeof(check));
priority_queue<in> PQ;
for(int i=0 ; i<A ; i++){
while(idx<T && arr1[idx].w<=X[i]){
PQ.push(arr1[idx]);
idx++;
}
while(!PQ.empty() && cx[i]<limit){
tot--;
cx[i]++;
check[PQ.top().idx]=true;
PQ.pop();
}
}
idx=0;
for(int i=0 ; i<B ; i++){
while(idx<T && arr2[idx].s<=Y[i] && cy[i]<limit){
if(check[arr2[idx].idx]){
idx++;
continue;
}
cy[i]++;
tot--;
idx++;
}
}
return tot==0;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
int xval=0, yval=0;
sort(X,X+A);
sort(Y,Y+B);
for(int i=0 ; i<A ; i++) X[i]--;
for(int i=0 ; i<B ; i++) Y[i]--;
if(A>0) xval=X[A-1];
if(B>0) yval=Y[B-1];
for(int i=0 ; i<T ; i++){
arr1.emplace_back(W[i],S[i],i);
arr2.emplace_back(W[i],S[i],i);
if(W[i]>xval && S[i]>yval) return -1;
}
sort(arr1.begin(),arr1.end(),cmp1);
sort(arr2.begin(),arr2.end(),cmp2);
int st=1, fn=T, mid, ret;
while(st<=fn){
mid=(st+fn)>>1;
if(pos(mid,A,B,T,X,Y)) fn=mid-1, ret=mid;
else st=mid+1;
}
return ret;
}
