#include "robots.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int cnt[100100], n, x, y;
int *a, *b;
pair<int, int> c[1001000];
bool col[1001000];
struct DSU{
int path[100100], e[100100], h[100100], sz;
void init(int n){
sz = n;
for (int i=0;i<n;i++) path[i] = e[i] = i, h[i] = 0;
}
int find(int s){
if (s==path[s]) return s;
return path[s] = find(path[s]);
}
void update(int s){e[s] = s+1;}
void merge(int s, int v){
int x = find(s), y = find(v);
if (x==y) return;
if (h[x]>h[y]) swap(x, y);
path[x] = y;
e[y] = max(e[x], e[y]);
if (h[x]==h[y]) h[y]++;
}
int _end(int s){
if (s==sz) return s;
return e[find(s)];
}
}dsu;
bool solve(int m){
///init
for (int i=0;i<x;i++) cnt[i] = 0;
for (int i=0;i<n;i++) col[i] = 0;
dsu.init(y);
///
for (int i=0;i<n;i++){
int tmp = dsu._end(c[i].second);
//if (m==2) printf("%d\n", tmp);
if (tmp==y) continue;
cnt[tmp]++;
col[i] = 1;
if (cnt[tmp]==m){
dsu.update(tmp);
if (tmp>0 && cnt[tmp-1]==m) dsu.merge(tmp-1, tmp);
if (tmp<x-1 && cnt[tmp+1]==m) dsu.merge(tmp, tmp+1);
}
}
int pt = x-1;
for (int i=0;i<y;i++) cnt[i] = 0;
for (int i=0;i<n;i++) if (!col[i]){
if (pt<c[i].first) return 0;
cnt[pt]++;
if (cnt[pt]==m) pt--;
}
return 1;
}
/*int main(){
scanf("%d %d %d", &x, &y, &n);
for (int i=0;i<x;i++) scanf("%d", a+i);
for (int i=0;i<y;i++) scanf("%d", b+i);
sort(a, a+x); sort(b, b+y);
for (int i=0;i<n;i++){
scanf("%d %d", &c[i].first, &c[i].second);
c[i].first = upper_bound(a, a+x, c[i].first) - a;
c[i].second = upper_bound(b, b+y, c[i].second) - b;
if (c[i].first==x && c[i].second==y){
printf("-1\n"); return 0;
}
}
sort(c, c+n, greater<pair<int, int>>());
//for (int i=0;i<n;i++) printf(" %d %d\n", c[i].first, c[i].second);
int l = 1, r = 1001000, ans = 1001000;
while(l<r){
int m = (l+r)>>1;
if (solve(m)) r = m, ans = m;
else l = m+1;
}
assert(ans!=1001000);
printf("%d\n", ans);
return 0;
}*/
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
x = A, y = B, n = T;
a = X, b = Y;
sort(a, a+x); sort(b, b+y);
for (int i=0;i<n;i++){
c[i].first = W[i], c[i].second = S[i];
c[i].first = upper_bound(a, a+x, c[i].first) - a;
c[i].second = upper_bound(b, b+y, c[i].second) - b;
if (c[i].first==x && c[i].second==y){
return -1;
}
}
sort(c, c+n, greater<pair<int, int>>());
//for (int i=0;i<n;i++) printf(" %d %d\n", c[i].first, c[i].second);
int l = 1, r = 1001000, ans = 1001000;
while(l<r){
int m = (l+r)>>1;
if (solve(m)) r = m, ans = m;
else l = m+1;
}
assert(ans!=1001000);
return ans;
}
