#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
#define task "main"
#define no "NO"
#define yes "YES"
#define F first
#define S second
#define vec vector
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
const int MAX_T = (int)1e6 + 6;
const int MAX_N = (int)5e4 + 4;
int numWeak, numSmall, numToy;
vector<ii> toys;
vector<int> weak, small;
int ans = 0;
bool check(int limit) {
priority_queue<ii> pq;
int iToy = 0;
FOR(i, 0, numWeak - 1) {
while (iToy < numToy && toys[iToy].F < weak[i]) pq.push({toys[iToy].S, toys[iToy].F}), iToy++;
int cnt = limit;
while (cnt > 0 && !pq.empty()) pq.pop(), cnt--;
}
for (; iToy < numToy; iToy++) pq.push({toys[iToy].S, toys[iToy].F});
FOD(i, numSmall - 1, 0) {
int cnt = limit;
while (cnt > 0 && !pq.empty() && pq.top().F < small[i]) pq.pop(), cnt--;
}
return (pq.empty());
}
int bs(int l, int r) {
int res = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) r = (res = mid) - 1;
else l = mid + 1;
}
return res;
}
int calc() {
sort(weak.begin(), weak.end());
sort(small.begin(), small.end());
FOR(i, 0, numToy - 1) {
if (upper_bound(weak.begin(), weak.end(), toys[i].F) != weak.end()) continue;
if (upper_bound(small.begin(), small.end(), toys[i].S) == small.end()) return -1;
}
sort(toys.begin(), toys.end());
return bs(1, numToy);
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
numWeak = A, numSmall = B, numToy = T;
weak.resize(numWeak);
small.resize(numSmall);
toys.resize(numToy);
FOR(i, 0, numWeak - 1) weak[i] = X[i];
FOR(i, 0, numSmall - 1) small[i] = Y[i];
FOR(i, 0, numToy - 1) toys[i] = {W[i], S[i]};
return calc();
}
/* Lak lu theo dieu nhac!!!! */
