#include "robots.h"
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string.h>
using namespace std;
const int INF=0x7fffffff;
struct robot{int w,s,wn,sn,n;}inp[1000010];
int a,b,t;
int np[50010],nq[50010];
int *check;
vector <robot> Ww[50010],Ss[50010];
vector <int> WL,SL;
bool comp0(const robot &a,const robot &b){return a.w!=b.w?a.w<b.w:a.s>b.s;}
bool comp1(const robot &a,const robot &b){return a.s!=b.s?a.s<b.s:a.w>b.w;}
bool comp2(const robot &a,const robot &b){return a.wn!=b.wn?a.wn<b.wn:a.sn>b.sn;}
bool comp3(const robot &a,const robot &b){return a.sn!=b.sn?a.sn<b.sn:a.wn>b.wn;}
bool solve(int x)
{
int i,C=0;
for(i=1;i<=a;i++)np[i]=0;
for(i=1;i<=b;i++)nq[i]=0;
for(i=1;i<=a;i++){
int u,j=i;
for(u=1;u<=x;){
if(np[j]==Ww[j].size()){
if(WL.empty())break;
else{if(j!=i)WL.pop_back();if(WL.empty())break;j=WL.back();}
}
check[Ww[j][np[j]].n-1]=1;
np[j]++;
C++;
if(C==t)return true;
if(np[j]==Ww[j].size()){
if(WL.empty())break;
else{if(j!=i)WL.pop_back();if(WL.empty())break;j=WL.back();}
}
if(u==x&&j==i&&np[j]!=Ww[j].size())WL.push_back(i);
u++;
}
}
WL.clear();
for(i=1;i<=b;i++){
int u,j=i;
for(u=1;u<=x;){
if(nq[j]==Ss[j].size()){
if(SL.empty())break;
else{if(j!=i)SL.pop_back();if(SL.empty())break;j=SL.back();}
}
if(check[Ss[j][nq[j]].n-1]){nq[j]++;continue;}
check[Ss[j][nq[j]].n-1]=1;
nq[j]++;
C++;
if(C==t)return true;
if(nq[j]==Ss[j].size()){
if(SL.empty())break;
else{if(j!=i)SL.pop_back();if(SL.empty())break;j=SL.back();}
}
if(u==x&&j==i&&nq[j]!=Ss[j].size())SL.push_back(i);
u++;
}
}
SL.clear();
return false;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
int i;
a=A;b=B;t=T;
for(i=0;i<A;i++)X[i]--;sort(X,X+A);
for(i=0;i<B;i++)Y[i]--;sort(Y,Y+B);
for(i=1;i<=T;i++){inp[i].w=W[i-1];inp[i].s=S[i-1];inp[i].n=i;}
sort(inp+1,inp+1+T,comp0);
int c=1;
for(i=1;i<=T;i++){
while(c<=A && inp[i].w>X[c-1])c++;
inp[i].wn=c;
}
sort(inp+1,inp+1+T,comp1);
for(i=c=1;i<=T;i++){
while(c<=B && inp[i].s>Y[c-1])c++;
inp[i].sn=c;
if(c>B&&inp[i].wn>A){return -1;}
}
sort(inp+1,inp+1+T,comp2);
for(i=1;i<=T;i++)Ww[inp[i].wn].push_back(inp[i]);
sort(inp+1,inp+1+T,comp3);
for(i=1;i<=T;i++)Ss[inp[i].sn].push_back(inp[i]);
int st=T/(A+B),en=T,mi,ans;
check = W;
while(st<=en){
mi=(st+en)>>1;
memset(check,0,T*sizeof(int));
if(solve(mi)){
ans=mi;
en=mi-1;
}
else st=mi+1;
}
return ans;
}
