#pragma GCC optimize("O3")
#include "robots.h"
#include<bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=1e6+50;
const int mod=1e9+7;
using namespace std;
int n,m,t,x[nmax],y[nmax],s[nmax],w[nmax];
multiset<pair<int,int> >sw,ss,st,nw;
multiset<pair<int,int> >::iterator it;
pair<int,int>p;
int ok(int tm)
{
int i;
sw.clear(),ss.clear();
for(i=1;i<=t;i++)
{
sw.in(make_pair(w[i],s[i]));
ss.in(make_pair(s[i],w[i]));
}
st.clear(),nw.clear();
it=sw.begin();
for(i=1;i<=n;i++)
{
for(;it!=sw.end();it++)
{
p=(*it);
if(p.fr>=x[i])break;
st.in(make_pair(p.sc,p.fr));
}
int ct=tm;
while(!st.empty() && ct--)
{
p=(*st.rbegin());
st.er(st.fd(p));
nw.in(make_pair(p.sc,p.fr));
if(ss.fd(p)!=ss.end())ss.er(ss.fd(p));
}
}
st.clear();
it=ss.begin();
for(i=1;i<=m;i++)
{
for(;it!=ss.end();it++)
{
p=(*it);
if(p.fr>=y[i])break;
st.in(make_pair(p.sc,p.fr));
}
int ct=tm;
while(!st.empty() && ct--)
{
p=(*st.rbegin());
st.er(st.fd(p));
if(sw.fd(p)!=sw.end())sw.er(sw.fd(p));
}
}
for(it=nw.begin();it!=nw.end();it++)if(sw.fd(*it)!=sw.end())sw.er(sw.fd(*it));
return (sw.empty());
}
int putaway(int N,int M,int T,int X[],int Y[],int W[],int S[])
{
n=N,m=M,t=T;
int i;
for(i=1;i<=n;i++)x[i]=X[i-1];
for(i=1;i<=m;i++)y[i]=Y[i-1];
for(i=1;i<=t;i++)
{
w[i]=W[i-1];
s[i]=S[i-1];
}
int l=1,r=t,mid;
while(l<=r)
{
mid=(l+r)/2;
if(ok(mid))r=mid-1;
else l=mid+1;
}
if(ok(r+1))return r+1;
return -1;
}
/*int main()
{
//freopen("sol.in","r",stdin);
//freopen("sol.out","w",stdout);
ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
return 0;
}*/
