#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;
ll t[N];
ll f[N];
ll a[N];
ll b[N];
ll w[N];
vector <int> id[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);
for (int i=0;i<T;i++){
if (W[i]>X[A-1] && S[i]>Y[B-1]) return -1;
ll p1=A;
ll p2=B;
if (W[i]<=X[A-1]){
ll z=lower_bound(X,X+A,W[i])-X;
t[z]++;
p1=z;
}
if (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;
}
// cout << p1 << " " << p2 << endl;
w[i]=p1;
}
ll l=0,r=N;
while(r-l>1){
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;
multiset <int> s;
ll p1=0;
for (int i=A-1;i>-1;i--){
for (auto u : id[i]) s.insert(u);
cnt+=a[i];
d++;
if (cnt-s.size()>mid*d){
p1=1;
break;
}
while(cnt>mid*d){
ll u=*s.begin();
b[u]++;
cnt--;
s.erase(s.begin());
}
}
cnt=0,d=0;
for (int i=B-1;i>-1;i--){
cnt+=b[i];
d++;
if (cnt>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
*/
