#include "robots.h"
#include <iostream>
#include <algorithm>
using namespace std;
struct node{
int w,s;
}id[1000004];
long long int temp[1000005],a,b,t,x[1000005],y[1000005],num[1000005];
bool cmp2(long long int tmp1,long long int tmp2)
{
return tmp1<tmp2;
}
long long int check(int m)
{
//cout<<m<<endl;
long long int p1=t-1,p2=a-1,now=0;
num[0]=0;
while(p1>=0 || p2>=0)
{
//cout<<id[p1].w<<" "<<x[p2]<<endl;
temp[0]=0;
while((id[p1].w>=x[p2] || p2==-1) && p1>=0)
{
temp[0]++;
temp[temp[0]]=id[p1].s;
p1--;
}
if(now<temp[0])
{
sort(temp+1,temp+temp[0]+1,cmp2);
for(int i=1;i<=temp[0]-now;i++)
{
num[0]++;
num[num[0]]=temp[i];
}
}
now=max(now-temp[0],(long long int )0);
if(x[p2]>id[p1].w || p1==-1)
{
now+=m;
p2--;
}
}
if(b*m<num[0])return 0;
sort(num+1,num+num[0]+1,cmp2);
//for(int i=1;i<=num[0];i++)cout<<num[i]<<" ";
//cout<<endl;
p1=num[0],p2=b;
long long int tmpnum=m;
while(p1>=1 && p2>=0)
{
tmpnum--;
if(tmpnum==0)
{
tmpnum=m;
p2--;
}
if(y[p2]>num[p1])
{
p1--;
}
else return 0;
}
if(p1==0)return 1;
return 0;
}
bool cmp1(const node &tmp1,const node &tmp2)
{
return tmp1.w<tmp2.w || (tmp1.w==tmp2.w && tmp1.s<tmp2.s);
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
a=A;
b=B;
t=T;
for(int i=0;i<a;i++)x[i]=X[i];
for(int i=0;i<b;i++)y[i]=Y[i];
for(int i=0;i<t;i++)
{
id[i].w=W[i];
id[i].s=S[i];
}
long long int l=1,r=t,ans=-1;
sort(id,id+t,cmp1);
for(int i=0;i<t;i++)
{
//cout<<id[i].w<<" "<<id[i].s<<endl;
}
sort(x,x+a,cmp2);
sort(y,y+b,cmp2);
while(l<=r)
{
long long int mid=(l+r)/2;
if(check(mid)==1)
{
ans=mid;
r=mid-1;
}
else l=mid+1;
}
return ans;
}
