#include "robots.h"
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#include <climits>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 1000100;
vector<pair<int, pair<int,int> > > w;
vector<pair<int,int> > s;
int a, b, n, x[maxn], y[maxn];
int cntx[maxn], cnty[maxn];
bool visited[maxn];
bool check(int steps) {
for(int i=0;i<maxn;i++) {
cntx[i] = cnty[i] = visited[i] = 0;
}
int last_j = 0, reached = 0;
priority_queue<pair<int,int> > pq;
/*for(int i=0;i<n;i++) {
cout<<w[i].first<<" "<<w[i].second.first<<" "<<w[i].second.second<<"\n";
}*/
for(int i=0;i<a;i++) {
for(int j=last_j;j<n && w[j].first < x[i];j++) {
pq.push(mp(w[j].second.first, w[j].second.second));
last_j = j + 1;
}
//cout<<i<<": "<<pq.size()<<"\n";
while(!pq.empty() && cntx[i] < steps) {
int last_ind = pq.top().second;
//cout<<"Deleting: "<<pq.top().first<<" "<<pq.top().second<<"\n";
visited[last_ind] = true;
pq.pop();
cntx[i]++;
reached++;
}
}
if(b == 0) return reached == n;
int curry = 0;
s.pb(mp(0,0));
for(int i=0;i<n && curry<b;i++) {
if(visited[s[i].second]) continue;
while((s[i].first >= y[curry] || cnty[curry] == steps) && curry < b) curry++;
if(curry == b) break;
if(s[i].first < y[curry]) {
visited[s[i].second] = true;
reached++;
cnty[curry] ++;
}
}
return reached == n;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
a = A, b = B, n = T;
for(int i=0;i<T;i++) {
w.pb(mp(W[i], mp(S[i], i)));
s.pb(mp(S[i], i));
}
sort(w.begin(), w.end());
for(int i=0;i<A;i++) x[i] = X[i];
for(int i=0;i<B;i++) y[i] = Y[i];
sort(x, x+A);
sort(y, y+B);
sort(s.begin(), s.end());
if(!check(T+1)) return -1;
int l=0, r=T;
int last_found = INT_MAX;
while(l<=r) {
int mid = (l+r)/2;
if(check(mid)) {
last_found = min(last_found, mid);
r = mid-1;
}
else {
l = mid+1;
}
}
return last_found;
}
/*int xx[maxn], yy[maxn], ww[maxn], ss[maxn];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int a, b, n;
cin>>a>>b>>n;
for(int i=0;i<a;i++) cin>>xx[i];
for(int i=0;i<b;i++) cin>>yy[i];
for(int i=0;i<n;i++) {
cin>>ww[i]>>ss[i];
}
cout<<putaway(a,b,n,xx,yy,ww,ss);
}*/
