#include"robots.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
using namespace std;
const int N=1e6+5;
int a,b,t,x[N],y[N];
bool vis[N];
vector<tuple<int,int,int>>order;
bool check(int lim)
{
for(int i=0;i<t;i++) vis[i]=false;
multiset<pii>cur;
for(int i=0;i<b;i++) cur.insert(mp(y[i],lim));
for(auto&x:order)
{
int w=get<0>(x);
int s=get<1>(x);
int id=get<2>(x);
auto it=cur.upper_bound(mp(s,1e9));
if(it!=cur.end())
{
vis[id]=true;
pii tmp=*it;
cur.erase(it);
if(tmp.se!=1) cur.insert(mp(tmp.fi,tmp.se-1));
}
}
cur.clear();
for(int i=0;i<a;i++) cur.insert(mp(x[i],lim));
for(auto&x:order)
{
int w=get<0>(x);
int s=get<1>(x);
int id=get<2>(x);
if(vis[id]) continue;
auto it=cur.upper_bound(mp(w,1e9));
if(it==cur.end()) return false;
pii tmp=*it;
cur.erase(it);
if(tmp.se!=1) cur.insert(mp(tmp.fi,tmp.se-1));
}
return true;
}
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];
order.resize(T);
for(int i=0;i<T;i++) order[i]=make_tuple(W[i],S[i],i);
sort(order.begin(),order.end());
reverse(order.begin(),order.end());
int l=1,r=T,res=-1;
while(l<=r)
{
int mid=(l+r)/2;
if(!check(mid)) l=mid+1;
else
{
res=mid;
r=mid-1;
}
}
return res;
}
/*
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int a,b,t;
cin>>a>>b>>t;
int x[a],y[b],w[t],s[t];
for(int i=0;i<a;i++) cin>>x[i];
for(int i=0;i<b;i++) cin>>y[i];
for(int i=0;i<t;i++) cin>>w[i]>>s[i];
cout<<putaway(a,b,t,x,y,w,s);
}
*/
/*
2 1 3
2 5
2
3 1
5 3
2 2
*/
