#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
vector <int> vec1;
int pr[1000100], sz[1000100], w[1000100];
vector <int> a, b;
int n, m, k;
bool f(int x){
int pos = 0;
multiset<int> q;
for (int i = 0; i < n; i++){
while (pos <= pr[i]){
q.insert(-sz[vec1[pos]]);
++pos;
}
for (int j = 1; j <= x; j++){
if (q.empty())
break;
q.erase(q.begin());
}
}
while(pos < vec1.size()){
q.insert(-sz[vec1[pos]]);
++pos;
}
for (int i = m-1; i >= 0; i--){
if (!q.empty() && -*q.begin() >= b[i])
return 0;
for (int j = 1; j <= x; j++){
if (q.empty())
break;
q.erase(q.begin());
}
}
if (!q.empty())
return 0;
return 1;
}
inline bool cmp(int fi, int se){
return w[fi] < w[se];
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
n = A;
m = B;
k = T;
for (int i = 0; i < n; i++){
a.push_back(X[i]);
}
for (int i = 0; i < m; i++){
b.push_back(Y[i]);
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
for (int i = 0; i < k; i++){
sz[i] = S[i];
w[i] = W[i];
vec1.push_back(i);
auto it = upper_bound(a.begin(), a.end(), W[i]);
if (it != a.end())
continue;
it = upper_bound(b.begin(), b.end(), S[i]);
if (it != b.end())
continue;
return -1;
}
sort(vec1.begin(), vec1.end(), cmp);
for (int i = 0; i < n; i++){
w[k] = a[i];
pr[i] = lower_bound(vec1.begin(), vec1.end(), k, cmp)-vec1.begin()-1;
//cout << a[i] << ' ' << pr[i] << endl;
}
//cout << endl;
int l = 1, r = k;
while(l < r){
int mid = (l+r)>>1;
if (f(mid))
r = mid; else
l = mid+1;
}
return l;
}
/**
3 2 10
6 2 9
4 7
4 6
8 5
2 3
7 9
1 8
5 1
3 3
8 7
7 6
10 5
*/
