#include "robots.h"
#include <bits/stdc++.h>
#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];
void preprocess(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());
}
bool check(int steps) {
memset(cntx, 0, sizeof(cntx));
memset(cnty, 0, sizeof(cnty));
memset(visited,false,sizeof(visited));
int last_j = 0, reached = 0;
priority_queue<pair<int,int>, vector<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++) {
// dodadi gi tija sto gi sobira
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++;
}
}
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[]) {
preprocess(A,B,T,X,Y,W,S);
if(!check(T+1)) return -1;
int index=T;
for(int cekor=T/2;cekor>0;cekor/=2) {
while(index-cekor>=0 && check(index-cekor)) index-=cekor;
}
return index;
}
/*int main() {
int a=3, b=2, t=10;
int x[3] = {6, 2, 9};
int y[2] = {4, 7};
int w[10] = {4,8,2,7,1,5,3,8,7,10};
int s[10] = {6,5,3,9,8,1,3,7,6,5};
cout<<putaway(a, b, t, x, y, w, s);
}*/
