#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,grS[N],grW[N],x[N],y[N],pW[N],pS[N],cntS[N],cntW[N];
vector<tuple<int,int,int>>order;
int FindS(int u)
{
if(pS[u]==u) return u;
return pS[u]=FindS(pS[u]);
}
void UnionS(int u,int v)
{
u=FindS(u);
v=FindS(v);
if(u==v) return ;
if(u>v) swap(u,v);
pS[u]=v;
}
int FindW(int u)
{
if(pW[u]==u) return u;
return pW[u]=FindW(pW[u]);
}
void UnionW(int u,int v)
{
u=FindW(u);
v=FindW(v);
if(u==v) return ;
if(u>v) swap(u,v);
pW[u]=v;
}
bool check(int lim)
{
for(int i=0;i<=b;i++)
{
cntS[i]=lim;
pS[i]=i;
}
for(int i=0;i<=a;i++)
{
cntW[i]=lim;
pW[i]=i;
}
for(auto&x:order)
{
int w=get<0>(x);
int s=get<1>(x);
int id=get<2>(x);
int go=FindS(grS[id]);
if(go!=b)
{
cntS[go]--;
if(cntS[go]==0) UnionS(go,go+1);
}
else
{
go=FindW(grW[id]);
if(go==a) return false;
cntW[go]--;
if(cntW[go]==0) UnionW(go,go+1);
}
}
return true;
}
int putaway(int A,int B,int T,int X[],int Y[],int W[],int S[])
{
a=A,b=B;
for(int i=0;i<A;i++) x[i]=X[i];
sort(x,x+A);
for(int i=0;i<B;i++) y[i]=Y[i];
sort(y,y+B);
order.resize(T);
for(int i=0;i<T;i++)
{
order[i]=make_tuple(W[i],S[i],i);
grS[i]=upper_bound(y,y+B,S[i])-y;
grW[i]=upper_bound(x,x+A,W[i])-x;
}
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);
}
3 2 10
6 2 9
4 7
4 6
8 5
2 3
7 9
1 8
5 1
3 3
8 7
7 6
10 5
*/
