#include <bits/stdc++.h>
#include "robots.h"
/// 500 485 462 A4
using namespace std;
typedef int ll;
typedef complex<double> point;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
//#define endl '\n'
//#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
const int N=1e6+10,inf=1e9;
ll t[N];
ll f[N];
ll a[N];
ll b[N];
vector <int> id[N];
ll par[N];
ll getpar(ll v){
if (par[v]==v) return v;return par[v]=getpar(par[v]);
}
ll h[N];
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
for (int i=0;i<T;i++) W[i]++,S[i]++;//
sort(X,X+A);
sort(Y,Y+B);
vector <pii> w;
for (int i=0;i<T;i++){
if ((A==0 || (A && W[i]>X[A-1])) && (B==0 || (B && S[i]>Y[B-1]))) return -1;
ll p1=A;
ll p2=B;
if (A && W[i]<=X[A-1]){
ll z=lower_bound(X,X+A,W[i])-X;
t[z]++;
p1=z;
}
if (B && S[i]<=Y[B-1]){
ll z=lower_bound(Y,Y+B,S[i])-Y;
if (p1==A)
f[z]++;
id[p1].pb(z);
p2=z;
}
if (p1!=A && p2!=B) w.pb({p2,p1});
// cout << p1 << " " << p2 << endl;
}
ll ans=0;
ll cn=0,dd=0;
for (int i=A-1;i>-1;i--){
cn+=t[i];
dd++;
ans=max(ans,(cn+dd-1)/dd);
}
sort(w.begin(),w.end());
if (B==0) return ans;
// if (w.size()) cout << 1/0;
ll l=-1,r=N;
if (ans>N) cout << 1/0;
while(r-l>1){
for (int i=0;i<A;i++) h[i]=0,par[i]=i;
for (int i=0;i<A;i++) a[i]=t[i];
for (int i=0;i<B;i++) b[i]=f[i];
ll mid=(r+l)/2;
ll cnt=0,d=0;
ll p1=0;
ll th=0;
for (int i=A-1;i>-1;i--){
cnt+=a[i];
d++;
if (cnt>min(inf/d,mid)*d){
th+=cnt-d*mid;
h[i]=cnt-d*mid;
}
cnt=min(cnt,d*mid);
}
// cout << "UH" << endl;
for (int i=0;i<w.size();i++){
if (th==0) break;
ll z=w[i].S;
// cout << z << " rjf" << endl;
// cout << getpar(z) << " " << h[z] << endl;
while(getpar(z)!=0 && h[getpar(z)]==0){
// cout << z << " " << getpar(z) << endl;
par[getpar(z)]=getpar(z)-1;
}
z=getpar(z);
if (h[z]){
h[z]--;
th--;
b[w[i].F]++;
}
}
if (th>0) p1=1;
cnt=0,d=0;
for (int i=B-1;i>-1;i--){
cnt+=b[i];
d++;
if (cnt>min(inf/d,mid)*d) p1=1;
}
if (p1) l=mid;
else r=mid;
}
return r;
}
/*
ll x[N],y[N],W[N],S[N];
int main(){
ll A,B,T;
cin >> A >> B >> 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];
// for (int i=0;i<T;i++) cin >> S[i];
cout << putaway(A,B,T,x,y,W,S);
}
2 1 3
2 5
2
3 1
5 3
2 2
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
*/
