#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define F first
#define S second
#define PB push_back
ll n,m,q,x[50005],y[50005],par[50005],res[50005],s[50005],u[50005];
P g[1000005];
vector<ll>cmx,cmy;
int find(int a){
if(par[a]==a)return a;
return par[a]=find(par[a]);
}
void unit(int a,int b){
par[a]=find(b);
}
bool check(int t){
for(int i=0;i<=cmy.size();i++)par[i]=i,res[i]=0;
for(int i=0;i<m;i++)res[y[i]]+=t;
for(int i=0;i<=cmx.size();i++)s[i]=0,u[i]=0;
for(int i=0;i<n;i++)u[x[i]]+=t;
for(int i=0;i<q;i++){
ll p=g[i].S;
p=find(p);
if(p==cmy.size())s[g[i].F]++;
else{
res[p]--;
if(res[p]==0)unit(p,p+1);
}
}
for(int j=cmx.size();j>=0;j--){
u[j]+=u[j+1];
s[j]+=s[j+1];
if(s[j]>u[j])return false;
}
return true;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int R[]) {
n=A,m=B,q=T;
for(int i=0;i<n;i++)x[i]=X[i]-1,cmx.PB(x[i]);
for(int i=0;i<m;i++)y[i]=Y[i]-1,cmy.PB(y[i]);
sort(cmx.begin(),cmx.end());
sort(cmy.begin(),cmy.end());
cmx.erase(unique(cmx.begin(),cmx.end()),cmx.end());
cmy.erase(unique(cmy.begin(),cmy.end()),cmy.end());
for(int i=0;i<n;i++)x[i]=lower_bound(cmx.begin(),cmx.end(),x[i])-cmx.begin();
for(int i=0;i<m;i++)y[i]=lower_bound(cmy.begin(),cmy.end(),y[i])-cmy.begin();
for(int i=0;i<q;i++){
W[i]=lower_bound(cmx.begin(),cmx.end(),W[i])-cmx.begin();
R[i]=lower_bound(cmy.begin(),cmy.end(),R[i])-cmy.begin();
g[i]=P(W[i],R[i]);
}
sort(g,g+q,greater<P>());
ll l=0,r=T+1;
while(r-l>1){
ll o=(l+r)/2;
if(check(o))r=o;
else l=o;
}
if(r>T)r=-1;
return r;
}
