#include<bits/stdc++.h>
#define ll long long
#define ld long double
#include "robots.h"
using namespace std;
int a,b,t,X[50001],Y[50001],W[1000001],S[1000001], flag = 1;
vector<pair<int,int> > f;
void count_max() {
int mxW = 0;
int mxS = 0;
for (int i = 0; i < a; i++) mxW = max (mxW,X[i]);
for (int i = 0; i < b; i++) mxS = max (mxS,Y[i]);
for (int i = 0; i < t; i++)
if (W[i] >= mxW && S[i] >= mxS) flag = 0;
}
bool solve (int d) {
int ptr = 0;
priority_queue<int> pq;
for (int i = 0; i < a; i++) {
int s = d;
flag = 0;
while (ptr < t && X[i] > f[ptr].first) {
pq.push (-f[ptr++].second);
}
while (s-- && !pq.empty()) {
pq.pop();
}
}
vector <int> v;
while (!pq.empty()) {
v.push_back(-pq.top());
pq.pop();
}
for (; ptr < t; ptr ++) v.push_back(f[ptr].second);
sort (v.begin(),v.end());
ptr = (int)v.size() - 1;
for (int i = b-1; i >= 0; i--) {
int s = d;
while (ptr >= 0 && s-- && Y[i] > v[ptr]) ptr--;
}
return (ptr < 0);
}
int putaway(int A1, int B1, int T1, int X1[], int Y1[], int W1[], int S1[]) {
a = A1; b = B1; t = T1;
for (int i = 0; i < a; i++) X[i] = X1[i];
for (int i = 0; i < b; i++) Y[i] = Y1[i];
for (int i = 0; i < t; i++) W[i] = W1[i], S[i] = S1[i],f.push_back({W[i],S[i]});
sort (X, X + a);
sort (Y, Y + b);
count_max();
if (!flag) return -1;
sort (f.begin(),f.end());
int l = 0, r = t;
while (l != r) {
int m = (l + r)/2;
if (solve(m)) r = m;
else l = m + 1;
}
return r;
}
