#include "robots.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10,maxm=1000000+10;
vector<pair<int,int>>allb;
vector<int>x,y;
int n,m,t;
int dp[maxm],p;
bool check(int mid){
for(int i=1;i<=t;i++){
dp[i]=0;
}
dp[0]=1;
int cnt=1;
for(int i=(int)allb.size()-1;i>=0;i--){
int p=lower_bound(y.begin(),y.end(),allb[i].second)-y.begin();
int ps=((int)y.size()-p)*mid;
ps=min(ps,cnt);
p=lower_bound(x.begin(),x.end(),allb[i].first)-x.begin();
int suf=(cnt)-((int)x.size()-p)*mid+1;
suf=max(suf,0);
for(int j=i+1;j>=0;j--){
if(j>=suf&&dp[j]==1){
continue;
}
if(j<=ps&&j!=0&&dp[j-1]==1){
dp[j]=1;
continue;
}
dp[j]=0;
}
// cout<<i<<" "<<mid<<" "<<ps<<" "<<suf<<" "<<allb[i].first<<" "<<allb[i].second<<" "<<dp[1]<<endl;
cnt++;
}
for(int i=0;i<=t;i++){
if(dp[i]){
// cout<<"ha: "<<i<<endl;
return 1;
}
}
// cout<<"nago"<<endl;
return 0;
}
int solve(){
int low=0,high=t+2,mid;
while(high-low>1){
mid=(high+low-1)>>1;
if(check(mid)==0){
low=mid+1;
}else{
high=mid+1;
}
}
if(low>t){
low=-1;
}
return low;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
n=A;
m=B;
t=T;
for(int i=0;i<n;i++){
X[i]--;
x.push_back(X[i]);
}
for(int i=0;i<m;i++){
Y[i]--;
y.push_back(Y[i]);
}
for(int i=0;i<t;i++){
allb.push_back(make_pair(W[i],S[i]));
}
sort(x.begin(),x.end());
sort(y.begin(),y.end());
sort(allb.begin(),allb.end());
return solve();
}
